Google Code Jam 2012 予選

家族の協力もあり、一日フルに使って Google Code Jam 2012 予選 に参加したところ、めでたく満点となり 89 位で終了しました。なかなか面白かったので感想をちょっと書きたいと思います。

答案はすべて Ruby で書きました。参加者が提出したコードは スコアボード からダウンロードできます。また自分のコードは github.com のリポジトリ に push しましたので、 コミットログ などを読めば、各問題にどれだけ時間をかけたのかもだいたいわかるでしょう。

朝

予選は日本時間で 4/14(土) 8:00 開始でしたが、開始時間を過ぎた後に目を覚まし、ふとんの中でスマホで問題を読んだ後に二度寝、結局とりかかったのは昼食を食べてからでした。

Problem A

サンプルの文字列からアルファベットの変換表を作って tr するだけの問題。

q と z はサンプルに登場しませんが、問題文に異なる文字に変換されるといったようなことが書いてある気がするので、勝手におたがいを交換するようなルールを追加したら通りました。

問題文中にも変換表の情報があったことについては 解説 を読むまで気づきませんでした。

Problem B

紙にメモを書きつつのんびり考えながらやってたら 1 時間くらいかかりました。遅すぎ。

Problem C

まただらだらと 1 時間くらいかけて C-small を回答。

最初の numbers.rb は [1000000,2000000] の計算に初代 MacBook (Debian sid) の Ruby 1.9.2p318 で 150 秒近くかかる状態で、これに C-large を食わせたら時間切れするのは明らかだったので、この後 1 時間ほど Ruby スクリプトの高速化に精を出しました。最初から C で書けばよかった。

最終版 numbers2.rb は [1000000,2000000] の答えを 15 秒で出せるようになりましたが、Mid 2009 MacBook Pro (OS X Lion) の Ruby 1.9.2p290 で動かしたら 8 秒足らずで終わってしまい、その差に驚きました。最終的に C-large はこの MacBook Pro で 120 秒ほどで解けました。

Problem D

この問題は見るからに難しそうというか、アイディアは浮かぶけど実装が面倒くさそうで気乗りせず、メシを食って子供をフロに入れて片付けをしてから、ようやく着手しました。

D-small を提出するまでに 5 時間かかり、D-large はさらに 1 時間後でした。書き上がったプログラムは他人のみならず自分にもあまり説明できる気がしません。

まあやってることは範囲円内の格子点めがけてトレースしてみて、元の位置に戻ってきたかどうかを見てるだけです。他の人の答案を見てると同じ方向の光線の判定に GCD を使ってる人が多いようでしたが、自分はベクトルの内積を用いました。

最初から D-large 向けの完全なプログラムを書いてしまったのですが、 D-small にはそういうことしなくても解ける簡単な方法があることを、 解説 を読んでから理解しました。

感想

あいかわらず自分はコード書くのが遅すぎなのが問題だと思いました。トップの人たちの答案を見てると、十数分とかそんな時間であんな簡潔なコードを書き下せているのが信じられません。

Code Jam 予選や DevQuiz みたいに、かなり長い持ち時間が与えられてだらだらと考えながらコーディングできるコンテストは気楽でよいです。いちばん自分の性にあっている気がします。

また Ruby は気楽に書けてよいのですが、large に挑戦するときに実行速度が問題になることが多いので、やっぱり最初から C/C++ で書いたほうがよさそうだと思いました。

次のラウンドも時間を作って参加したいと思います。こんどは短期決戦なので、書くのが遅い自分が突破するのは難しいかもしれませんが。

2012/04/15 04:33:00 JST