9thでした。Hardが簡単めだったので、解きたかったです。Easy(215.96/250) わぁい撃墜 あかり撃墜大好き(Easyでは撃墜していません) 色々面倒なだけ。 class AkariDaisukiDiv2{ public: int countTuples(string s) { int len = s.size(),ans=0; for(int i = …

4時間のコンテストでした。 A. n×nの行列の対角と中央の行と列にある数字をすべて足します。 普通に足して、中央の数字の3倍を引いても良いです。 int g[128][128]; int main(){ int n,ans = 0; cin>>n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; …

60pts(3703th)で通過。A. やるだけ。中括弧を使ってしまったのは反省しなければならない。 char decoding[] = {'y','h','e','s','o','c','v','x','d','u','i','g','l','b','k','r','z','t','n','w','j','p','f','m','a','q'}; int main(){ int T; string s; …

実装するだけですが、こういうの(構文解析?)に慣れてないから、実装が結構難しかったです。 整数が1桁だと思い込んでいるとWAします。 #include <iostream> #include <string> using namespace std; string s; int single(int& pos); int figure(int& pos); int solve(int& pos</string></iostream>…

まず、逆向き(プレゼントを拾う方向)に考えると探索空間が減ることが、この問題の重要な性質です。これに気が付かないとAOJでは通せないと思います。AOJの場合、実行時間制限とメモリ制限が厳しく、ナイーブな探索やDPでは解けないので、少し工夫する必要が…

Easy(122.18/250) 条件を注意して読みましょう。最初からちゃんと読んでいれば、余裕で240点代出せます。 バグ対策[要出典]にソートした人はあまりいなさそうでした。 #include <algorithm> #include <cmath> #include <ctime> #include <iostream> #include <string> #include <vector> using namespace std; cl</vector></string></iostream></ctime></cmath></algorithm>…

横棒を通るときに、番号をその棒に記録しておけば、もう片方から来たときにO(1)で交差してることが分かります。 交差を切ることで、得点を入れ替えることができるから、最も得点差(点数を減らせる量)の大きいものを求めれば良いです。 #include<cstdio> #include<cstring> #in</cstring></cstdio>…

愚直に全てシミュレーションするとTLEするので、N-1回散歩した後の地図を求めます。 ある点をn回通るとき、 (i) nが偶数のとき、東と南にn/2回ずつ通る (ii)nが奇数のとき、最初に書かれていた文字の方向に(n+1)/2回、もう一方に(n-1)/2回通る よって、通過…

特定の区間に足し算をするのを高速(全体でO(n+m)くらい)に行えば良いから、累積和で解くことができます。 #include<cstdio> #include<algorithm> using namespace std; #define MOD 100000 int inn[100000],walk[100001]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i </algorithm></cstdio>…

動的計画法で解けます。引っかかる人はほとんどいないかもしれませんがコーナーケース(最初が0のとき)があります。 #include<iostream> using namespace std; typedef long long ll; ll dp[100][21]; int data[100]; int main(){ int n; cin>>n; for(int i = 0; i < n;</iostream>…

まともに書こうとしたが、諦めた p:10000

*./ 1+i.20

J言語使うと簡単 q:が素因数分解する動詞です。 {:q:600851475143

1000未満で且つ、3か5の倍数である自然数の和を求める全くJらしくないですが、Jです。 (+/ 5 * 1+ i.199) + (+/ 3 * 1 + i.333) - (+/ 15 * 1 + i.66)多少改善 +/ ~. (5 * i.200),(3 * i.334)

" 入力例 2 において，あなたには友達はいない．"単一始点最短路を求める問題。 普通にダイクストラ法やワーシャルフロイド法するのは面白くないので少しだけ違う解き方をしました。想定解法とあまり変わらないみたいです。 #include<iostream> #include<cstring> #include<algorithm> usin</algorithm></cstring></iostream>…

DFS(深さ優先探索)の典型問題。m+2 × n+2のマップを使うとマップ外に出なくなるのでオススメです。 #include<cstdio> #include<algorithm> using namespace std; int m,n,unused[90][90],dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; int dfs(int y, int x, int d){//座標と、今までに</algorithm></cstdio>…

実装。色の変え方が最大で2パターンあるので、両方とも試す。 #include<cstdio> #include<algorithm> using namespace std; int n,chain[10000]; int fig(int b){ int a = b-1,c = b+1,color,res = 0; if(a>=0){//b == 0のバターンを弾く int s = 1; color = chain[a]; while(a></algorithm></cstdio>…

動的計画法で解きました。INFで初期化する代わりに-1で初期化してます。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,x[151][11],d[150][11],dp[150][10][77]; const int INF = 1000000000; int main(){ while(scanf("%d%d",&n,&m),n){ memset</cstring></algorithm></cstdio>…

共通部分文字列の長さの最大値を求める問題。 1文字後ろを調べ、同じ文字列を重複して調べないようにすると、TLEしないで解けます。 O(n^3)かO(n^2)です。 #include<iostream> #include<string> #include<algorithm> using namespace std; string s,t; int main(){ while(cin>>s>>t){ int </algorithm></string></iostream>…

辺が増えていく最短経路問題。増えた辺を使うと経路が短くなる場合があるので、それを調べます。(増えた辺を使わないで経路が短くなることはない) O(kn^2)です。AOJではギリギリ通せなかったのですが、ワーシャルフロイド法(や、その他の最短路のアルゴリズ…

最大値の伝播で解くのは難しそうだったから、累積和で解きました。 少し枝刈りしましたが遅いです。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int g[10003][10003]; int n,r; int main(){ while(scanf("%d%d",&n,&r),n){ memset(g,0,sizeof(g)); in</algorithm></cstring></cstdio>…

Div1は550を誰かが解かないとノーコン(Div1)になるらしいです(2012/04/15 15:01) 問題見てみたいけど、Div2だと見れないみたいです。practiceに入りました。 Easy(174.03 / 250) 遺伝子の情報が与えられて、1つの家族として考えられるものの中で、最も人数の…

Rが小さいので、行単位でひっくり返すのは全て試します。 列は自由にひっくり返すことができるため、表になっているものの個数か裏になっているものの個数の内大きい方を使えば良いです。 数えるのにO(RC)かかるので、全体ではO(RC･2^R)になります。 #include<cstdio></cstdio>…

星座にある星(固定しておく)から写真にある星までのベクトルを考えれば、並行移動の仕方はn通り あることが分かります。n通り全て試すためには、1通り試すのにO(m+n)やO(mlogn)程度で良いです。辞書順にソートしておくことで、O(n^2+mn)で解くことができます…

文字列から"JOI"と"IOI"を検索する 2文字目と3文字めが共通しているので、1文字目は後で考えると少し速くなりそうです。 #include<iostream> #include<string> using namespace std; string s; int main(){ while(cin>>s){ int a=0,b=0; for(int i=1,l=s.size()-1;i</string></iostream>

太郎が持っている:1 花子が持っている:0 残ってない:-1のようにすると、配列1つと単純なループで解くことができます。(入出力も簡単) #include<iostream> #include<cstring> using namespace std; int card[200]; int main(){ int n; while(cin>>n,n){ memset(card,0,sizeof(car</cstring></iostream>…

A. 前から数える。本番ではstring s[3000]としてRE #include <iostream> #include <string> using namespace std; string s[30000]; int main(){ int n,ans = 0; cin>>n; for(int i = 0; i < n; i++)cin>>s[i]; int f = 1; for(int i = 0,l = s[0].size(); i < l && f; i++){ c</string></iostream>…

メモ化再帰で解きました。 順番にモビールを選び、そこから下のモビールの重さ(の最小値)を再帰的に求めます。 重さ * 長さ = モーメント なので、両方のモーメントを求めて、整数倍(最小公倍数を求める)し釣り合わせます。 重さ = モーメント / 長さ で、重…

点A(a,b)と点B(c,d)があるとき、a A,Bを探すときは、入力された順に辿って行き、正方形ができているか調べるときは、辿らずに直接調べることで、O(n^2)になります。(全部辿るとO(n^4)になる) #include<cstdio> #include<cstring> using namespace std; int x[3000],y[3000],n,</cstring></cstdio>…

しゃくとり法で数えます。 0 2 3...n のときに、変な動作をしますが、撃墜はされません(他にコーナーケースがあるかもしれないけど、ACはできました) #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> using namespace std; bool card[100020]; int n,k; int main()</cstring></cstdio></iostream></algorithm>…