Google Code Jam 2009 Round1A備忘録

GCJ2009のRound1Aをやったので備忘録などなど

"UWI"で参加してます。
本当は1B,1Cをやる予定だったのだが、なぜか早起きしたのでせっかくだしやるか、ということで寝ぼけながらやった。特に目標何問というわけでもなく適当にやった。

はじめにA問題、コラッツっぽいやつかという印象。だが問題文を読み違えて、"2 3"なら、2と3に行き着くような共通の数を探せとか読み取ったのでうあーめんどそうだなーとか思いパス。

B問題、変数大杉、パス。

C問題、C種類のカードをコンプするのに必要な、異なるN種類のカードがはいったブースターパックの個数の期待値を求めよという、非常に身近な問題。コンビネーション使って解けそうだなーと思ったのでこれを先に解く。期待値を求める式から、残り種類数を引数としたDPで行けると思ったけれど、サンプルがとおらなかった。自分に返ってくるのもある模様。
ちょっとめんどいなーと思っていたらA-smallがサクサク解かれていたので、もしかして簡単なのかなと思って問題見直す。読み違いに気づいて、これだけ正解しているなら愚直な方法で行くだろうと思って愚直に解く。通る。(36ぷん)

で、Cに戻る。自分に返ってくるとはいえ、移項してしまえばなんてことはなかった。サンプル通る。smallも通る。largeは、実行しはじめたらすぐには終わらなかったので、あせってメモ化を実装してsubmit. (49ふん)

A-largeを見る。ここでまた読み違い。1<=T<500というのをみて、「base=500とかの場合があるのか、うへぇ、特殊なとき方じゃないと解けないな」と思い込んで、Bを解くことに専念し始める。終了後に、Tは本当は問題数と気づいたけど、それでも若干工夫が必要だったのでどっちもどっちだった。

B-smallを解く。各cornerを頂点にしてdijkstraで行けると思った。サンプルも通ったが、smallが通らない。すぐにrowが逆順なことに気づくが、それでも通らない。dijkstraで解けるのであれば、B-largeも通るはずなので、これ一問に専念していた。
で、だらだら1時間半がすぎ、終了。49点の239位。

結局、row, colを逆行する(目的地とは反対の方向に行く)処理を書いてなかったことが原因とわかった。その処理を加えたらsmallもlargeも通る('A`) 非常に悔しかった。

dijkstraは、Roundがはじまる20分前に下処理を書いていたのであたったと思ったのに慢心というか見落としというか・・
あとは問題文の読み違いが去年に引き続き多い。ちゃんと読まないと・・