Sample InputSample OutputSample Solution ｗｗｗｗｗｗｗｗｗ

反復深化で47ms。その後実験でBFSしてみたらTLEｗｗｗ 最悪 (50+座標) * 4^10 byte 必要なのでメモリ的にも危ないとは思ったけど。

http://www.acm.inf.ethz.ch/ProblemSetArchive.html アーカイブを発見。sample inputとoutputをゲットしてデバッグ完了！1000000000*3は負になっちゃいますよね／(^o^)＼ それだけでした／(^o^)＼

例のめんどくさい問題をそろそろ解こうかと思って実装してみた。だけど、ランダムでデータを生成したりしながら、正解のプログラムと答えを比較して全部一致したのにWA…。一番厄介なパターン。だるくなったので終了。また今度1から組み直してみる。なんか条…

ちょっと訳ありで速くしてみた。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; struct Data { const char* s1; int l1; const char* s2; Data(const char* s1, int l1, const char* s2) : s1(s1), l1(l1), s2(s2) {} char operator [](int</algorithm></vector></string></iostream>…

http://acm.pku.edu.cn/JudgeOnline/problem?id=2684 久々にやった。今年は頑張って東大勢とさいたま+その他大勢の猛者に勝つ！今年はほぼ確実にawakiaと出れる最後のICPCなので気合い入ってます。もう一人の新チームメイトもポテンシャルがやばいので気合い…

昨日の反省をふまえてLCSを色々作ってみた。昨日のfox(笑)のid:awakia-n案も実装してみた。結構綺麗に出来たと思う。O(NM)。合ってるか分からんけど。考え方。LCSの性質上、文字列x, yの順序を逆転した物をx', y'としたとき、lcs(x, y)とlcs(x', y')の内容は…

違う問題で見かけた陰険インプットを見てひらめいた。実はちゃんとDPできてた。そしてなんで解けないのか分かった。0 0だけで構成されるケースでWAが出てただけでしたorz 道の再構築にsetとか使ってるせいでオーダーがでかくなっちゃってるのでその辺をどう…

DPができねぇ。

プチEdit Distance。一文字置換、一文字挿入、一文字削除に限定してチェックすればいい。また、辞書の要素数が最大10000で、チェックする文字列は最大50。一回TLE出してから気付いたのが終わってるけど、チェックする文字列に対して何か処理をして、線形に探…

1984MSで通したｗ O(N^2logN)だけど実際はO(N^2log(N^2))。もうちょっと色々と減らす方法考えないと。追記: 765MSになった。今度こそ正真正銘O(N^2logN)。後は何かできるかなー。

main(h,m){for(gets();~scanf("%d:%d",&h,&m);)printf("%d\n",m?0:(h+11)%24+1);}30分くらいで76Bにできた。嬉しかった。

main(a,b){for(gets(b);~scanf("%d%d",&a,&b);puts(a

O(N^2logN)の方法を思いついたけどWAが出る。けど、awakiaに教えて貰った双対変換がヤバイ。東大だと授業でやるそうで。壁を感じたｗ

単なる階乗の時なら効率よく処理する方法思いついたけどPだと混乱する。落ち着いて考えれば出来そう。

科目登録しねーとと思いつつもPKU。線分の交差判定。「繋がってる」っていう関係が推移律を満たすので、disjoint setで繋がってるかどうか判定してみたけどおせー。とりあえず幾何ライブラリテストとしてはおｋだけど高速化してみないとダメだ。高速化: O(N^…

素数判定っぽい問題。100B切りたい(´･ω･｀) a['aa'],i; main(k,n){ for(;++i<9994;) if(!a[i]){ printf("%d\n",k=i); for(;k<9994;a[k]=1) for(n=k;n;k+=n%10,n/=10); } }ていうかなんだこの適当なプログラム…。

156Bの壁

WA8回とか／(＾o＾)＼ 最初にlongを使ったことが全ての始まりだった。なんだこれ実は32bitじゃなくね？32bitっつーのは32bit Pascalの事で、そのLongIntって実は64bitなんじゃね？ふざけんなーｗ ↓ あれｗｗｗまだWA出るｗｗｗうはｗｗｗ ↓ 綴り間違ってない…

a,b,m,p,q,n; main(s){ for(;~scanf("%d%d",&a,&b);printf("%d %d %d\n",a,b,m),m=0) for(p=a

いきなりショートコーディング: 155Bｷﾀｰｗ 反則なのかどうなのかはおいといて、とりあえずコード。 a,b,m,p,q,n; main(s){ for(;~scanf("%d%d",&a,&b);m=0){ for(p=a

awakiaと2000番台から適当に選んで解こうぜｗｗｗうぇｗｗみたいなノリになりながら適当に「じゃー2040でｗｗｗ」とか言ったからこの問題を解いた。調子に乗ってやった。その場で反省した。内容はグラフの同型判定。で、とりあえず多項式時間では解けなそう…

リベンジ完了。1018に関しては、以下に早い段階で枝切りが出来るかが重要だった。実はバックトラックが必要ないのでループで書けたことが発覚。awakiaに感謝。1016は前に解いたときにドツボにはまってもがいてたんだけど今日やったら通った。一体何だったん…

どこをどう見てもブロックソーティングだよなぁ…って思ってそのまま実装したら通った。ショートコーディング: 163BになったけどWAが出たｗ うへー。疲れたからいいや。

眠かったけど微妙に眠れなかったので簡単な問題さがしてたけどこれはさすがにすいませんでしたとしか言いようがありませんでしたorz ちゃんと自分でも書けるようにしときまｓ。ショートコーディング: 実はまだ買ってきた本を読めてないので全然効果は出てな…

面白そうだからやってみたけどむじー。適当にやったらMLE出た。ボトムアップに個数を数えてボトムアップに何番目か計算していかないと死んでしまう模様。ちょっと色々考えてみる。

漸化式にならないなら再帰のプログラム書いてからそれをDPに直せば良いじゃん。俺は人生で数式よりもプログラムに触れてた時間の方が32倍(当社比)くらいなげーんだよ！って開き直って適当に再帰で書いてみた。 bool search(int sum, int target) { for (int …

M本氏に感謝ｗ 解けーた。既に和の部分が求まっていて、x+y=nのxとyが未知な覆面算として解いた。しかし、覆面算と言っても4桁の場合なら A B C D + B C D --------- A B C D + A C D --------- A B C D + A B D --------- A B C D + A B C --------- 多くて…

数学的に解かないと無理っぽい即死。追記: M本氏のアイディアで、n桁のNに対して覆面算をn個の覆面算を解くようにしたら行けるんじゃないかという説が浮上。頭が回復したらやってみる。

ただのシミュレーション問題。ショートコーディング: 319Bまで減った。改行コード変えれば後5B減る。猛者い人達なら余裕でもっと減らせるんだろうなぁ。疲れたからもういいやorz #include<stdio.h> #define C(D)d[t&1][y*22+x D] #define N d[t&1^1][y*22+x] #define </stdio.h>…