Google Code Jam Round 3

http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiM4AYM

不調もこんだけ続けば実力だな。
もう自分が勝ってる姿をどうにも想像できない。
A両方とC-smallとD-smallを通して35点。
Bが書き終わらなかったたたたた!
今回はしょうもないバグをあんまり埋め込まなかったので、
Round2よりはだいぶマシだったのだけど。


今回、前回の教訓を生かして、
マルチスレッドでテストケースを処理するプログラムを書いた。
おかげさまでテンプレートが150行を越えた。
なので今回はもうC++で突っ切る。
Haskellはとてもじゃないけどいろいろ準備する時間が無かった。

A

縦横のラインからなる図形が与えられるので、
「ポケット」の面積を求めよ。
ポケットとは、図形の外でかつ上下、または左右に壁があるところ。


問題を読んでる途中に5pt獲得者が続出。げんなり。
正直ぱっと見簡単に見えなかったのだけど、
どうにもA以外からやるのは気が乗らなかったので、やっぱりAから。
内側と外側を塗り分けてごちゃごちゃやってるうちに30分以上消費。
おいおい…。

D

このままではダメだと思ってDに切り替え。
解いてる人多すぎ。
右下にのみ移動できるナイトで座標(1,1)から(N,M)に行く方法の数を求めよ。
ただし、盤上にはいくつか穴が開いてる。

smallがやはりとても簡単。
適当に終わらせる。
しかし、剰余演算子を&と書いてしまって1回Wrong。
びっくりだ。

C

順位が厳しかったので、点数の高いCに移動。
カンニングされるような配置を避けて、机に生徒をなるべく多く配置せよ。
これまたSmallは簡単だったの適当に書いて終了。

A

Bを一応見てみたけど問題が長かったので、一旦Aに戻ることに。
よく考えると縦と横にスキャンして、内部と内部の間の区間をとるだけで
SmallもLargeも通るような気がしたので、100行近く書いた最初のコードを破棄して書き直し。
壁は座標を二倍化してさっぱりとした表現に変更。
さっきとはうって変わってシンプルなコードが完成。
Smallを通して、念をいれて少し最適化してからLargeをサブミット。

B

CとDを考えるかBを解くかで、Bを解くを選択。
ワープポイントを作ってワープができる迷路上の最短距離。
問題を読み終わった時点で残り20分ぐらい。
どう見ても幅優先で、SmallもLargeも両方間に合うはずだったんだけど、
設計が悪かったせいか、書いても書いても終わらない。
残り1分を切った頃にテンプレートと合わせて300行ぐらいのプログラムが完成したのだけど、
サンプルが通らなかった。残念。

反省

AとBのコーディングの筋が悪すぎた。