GCJ 2013 Round1B

参加ログ その他

通過してない。
AとC-smallだけ通した。
なんかPCの調子が悪くて最初の20分ぐらいPC再起動を繰り返してた。

A.Osmos

smallとlarge。

どんどん太っていく、、、
貪欲っぽいけど、選ぶのがなくなったら、消す場合と追加する場合の2択していけばよさそう。
再帰だとlargeがあやしい？のでqueueで。

B.Falling Diamonds

未提出。
Cやってから問題だけ読んだ。
残り10分で、シミュレーションしか思いつかなかったので、間に合わず。

C.Garbled Email

smallだけ。

形態素解析っぽいので、こっちを優先。
dp[i][j]:=j個前が違っている場合の、S[0..i-1]の部分文字列の最小間違い個数
というのを考えるとdp[4000][6]ぐらいで行けそう。
smallは50*5*520000=1.3*10^8ぐらいなので、単純に回してもよさそう→不等号間違ってて2WA。
largeは4000*5*520000=1.04*10^10とかになってしまうので、せめて520000のところを5000ぐらいで済まさないといけない。。。
ちょっと書き換えたけど、間に合わなそうなので、ファイルの記念ダウンロードだけ。