Google Code Jam Round3 負けました

(2008-08-15追記 問題Bについて大嘘を書いてますので、http://d.hatena.ne.jp/matsuza/20080815/1218770400:コチラを参照してください)

1000人中500人通過の所、883位(5点、1:20:41)で落ちました。
合格ラインは15点(1:07:39)だったので、全然ダメですな。

A. How Big Are the Pockets?

問題文が解りやすかった && A問題のSmallは簡単だろう(あわよくばLargeも)という判断で解き始めたんですが、いや時間がかかるかかる。
着手率も低く、A問題に手を出した人の通過率も惨憺たるものだったので、これは僕が手を出すべき問題じゃなかったみたいです。
ポリゴン内外部判定問題の親戚と考えて解きました。Small正解。

B. Portal

全く問題を読まず、着手もしませんでした。着手率も低かったようなので。
で、読み直してみたら……A*アルゴリズムでゴールに到達する問題じゃん!簡単だよこれ!
今解いてみたら一時間ちょいでLargeを通せるプログラムが書けました。Small+Largeで25点(300位前後)だったんで、最初からこれに着手してれば良かったんだな……。
ただ、この問題のLargeは計算速度が速い環境でないと解けないようなので(うちの環境で上位入賞者のプログラムを動かしてみたら8分超えた)、ちょっと、うーんという感じ。僕のプログラムもJava+マルチスレッド化してようやく5分弱というところだし。Rubyなんかだと時間内に解けないんじゃないかな。

C. No Cheating

全く問題を読まず、着手もしませんでした。
着手率、正解率ともに良かったので着手すれば良かったかな?と思って問題文を読んでみたのですが……なんでみんなこれに正解できるのか解らん。

D. Endless Knight

Small問題だけ手をつけたのですが、なぜか正解できず。アホなミスを事後に発見するも時遅し(正解しててもポイント不足で500位には到達できてないですが)。

反省

いや流石に厳しかった。

最初に、作戦レベルの反省から。
まず全ての問題文に目を通してから問題に着手すること。いざとなると頭に血が上って読めないんですよね。で、読めた先から着手しちゃう。僕の場合、今回はB問題から手をつけるべきだったんですよね。

次に、戦術レベルの反省。
コンテストに適した書き方に慣れ、練習すること。例えば、forやifに続くのが単文なら{}を省略する、とか。座標を表すのに、クラスを作ったりintの配列を作ったりするのではなく、x1, x2等で簡単に書いちゃうとか。java.lang.Mathなんかはimport staticしておくべきだろうし。
コンテスト慣れしてるC++使いの人なんかは、マクロを駆使してコンテスト用特殊工具みたいなコードのテンプレート使ってますし。見習っても良いかもしれない。というかC++は強いよねこういうの。C++に乗り換えるのも検討してみようかな。C++で解きにくい問題は出題されないだろうし。

最後に、戦略レベルの反省。
アルゴリズムの勉強しなきゃダメだなあ。語彙の有る無しで展開が全く異なってしまう。例えば、B問題なんかは誰でも知ってるアルゴリズムだとSmallしか解けなくて、A*アルゴリズムを知っていないと(あるいは再発明しないと)Largeを解けないんです。
Knuth先生の本、読み直そう……。

来年はローカルオンサイトラウンド選出を目指す!