Google Code Jam 2012 Round 1B 参加記

他所様のコンテスト参加記を読むのが楽しいので、自分も書いていこうかなと思い立ちました。余力や記憶が残っている時だけ書こうというスタンスです。AOJで解ける問題が少なくなってきたので、こういう形でもブログを頻繁に更新できたらいいな、とも思っています。

えっと、とりあえず結果を

順位	得点	ペナルティ
466th	63	2:26:16
A-small	A-large	B-small	B-large	C-small	C-large
57:12 1WA	58:00	2:19:59	2:22:16	1:21:23	未提出

無事、Round 2へ通過できたようです。GCJJ出たことありますがGCJに出るのは初めてで、Round 1通過は素直に嬉しいです。
以下、思い出せる限りの思考の変遷です。

開始前

仮眠したり風呂に入ったりして、本番中眠気が来ない状態にしておく。
扁桃腺が腫れてるようで喉のコンディションがやばかったけど、本番中は何かの拍子に奇声を上げるくらいしか声を出さないのでモウマンタイ。
ポカリ、蟻本などの準備
Eclipse、ライブラリ、GCJテンプレートなどの準備
開始直前までtwitterで適当な発言をして暇をつぶす

開始

うおー始まったぜー
各問題の配点など目もくれずに、A問題から順に取り組んでいく

A問題をゆっくり確実に読解しようとする
読み終えた
えーと、つまり点数で勝てばいいんでしょ？
（ここで、「オーディエンスがどのように点を分配しても」という条件を部分的に思い出す）
あー、どんな場合でも勝たなくちゃいけないから自分以外の人の中で最高得点の人に点が集まるのが最悪ケースかー（←勘違い発動）
この最悪ケースでも勝てるための最小パーセンテージが答えじゃないか
書く
サンプル合わない
あー100倍してなかったわー
合わない
どーいうこと？
問題読み直す
なんで1番になろうとしてるんだよ、ビリじゃないもしくはビリと同点にさえなりゃいいんじゃないか
自分以外の一番得点が小さい奴と同点になるための最小パーセンテージじゃないか
直す
サンプル合わない
あー、得点上げていくと、別の奴が最低点になるケースがあって、もっとパーセンテージ減らせるなー
反例が見つかったので直す
サンプル合った！
提出する
Incorrect!!
ﾌｫｯ！？
あ、得点の昇順にソートしてねーや。ソートしなくても確かにサンプルは合うなこれ
直して提出する
A-small Correct
計算量も大したことないからlargeも間に合うだろう
A-large Submitted

この時点で1時間近く時間使って焦る
スコアボード見るとみんなC-small解いてる。6点！？さぞかし簡単なんだろう

C問題読む
なるほど、部分集合列挙するだけじゃね？
列挙して、和が同じになるようなsとS-sを見つけようとする
別に、和集合が元と一致する必要ないじゃん
和をキーにしたMap作って集合蓄えよう
書く
サンプル合う
C-small Correct

この時点で900位台半ばくらい(だったはず）
B解かないとアウトだこれ・・・、と焦り始める
B-largeは考えずにsmallだけでも通す心意気で臨む

B問題読む
すごく長い
ノートに重要事項を書きだしていこう
カヤックって聞いたことあるけど知らんなぁ
読み終える
残り時間40分くらい、何とか間に合うか？
えーと、水が引く前に好きなだけ動けるから、行ける場所をBFSで列挙しよう
（位置、水の高さ）のダイクストラで解けるだろう
水は1秒で10cm引くから、0.1秒を時間の単位にしよう
0.1秒単位などで混乱しながらダイクストラ書く
サンプル動かす
全然合ってない・・・
なんでだ？
あ！！水が引く前のBFS間違えてら！！
直す
サンプル動かす
4番目だけ合わない
なんでだ？
をおおい、等号忘れてるよ！
直す
サンプル合う！
残り時間確認する。あと10分くらい！
提出
頼む！通れ！デバッグする時間あんまりないんだ！
B-small Correct
っしゃあああああああああ！（リアルガッツポーズが出る）
ここでたしか600か700位台なので、A-largeが通れば十分通過できると確信する
冷静にB-largeの制約を見てみる
あれ？頂点数10^8程度のダイクストラって行けるんじゃね？
残り9分
largeの時間制約は8分なので、試しにやってみることにする
結構早く終わる
B-large Submitted

これで満足してtwitterに舞い戻る

コンテスト終了

AもBもlargeが通ってRound1通過決定！

感想

Aに時間を取られすぎですね。なんというか、出力が浮動小数点だと、うわ苦手な幾何か確率とかだわ、と日和るんで冷静さが失われる弱点があるようです。
そのあと、スコアボード見て、C-smallだけ通したり、冷静に長文のBを読んで着実に解けたのでかなり挽回できたみたいです。要所をノートに取ったのはかなり効いたと思います。
Round 2は更にエグイ難易度の問題が出そうですが、Tシャツ狙って頑張りたいと思います
あと、今スコアボート見たら順位が1つ上がって465thになってました