Google Code Jam 2012 反省会

Google Code Jam 2012 の Round 1 は A B C すべて参戦しましたが、結局全部情けない成績で おちました 。 予選で満点 がとれて浮かれていましたが、やはり甘くなかったようです。来年またがんばります。

記憶を風化させないためにも各問題の所感などを書いていきたいと思います。

2012/05/08 追記: github.com に書いたコードを push しました (予選のときに比べてあまり整理されていません)。あわせてこの記事の一部を書き直しました。

Round 1A

Password Problem

C++ の速度を過信して最初に再帰で全探索する プログラム を書いてしまい Large が解けず終了。コンテスト終了後に考え直したら数秒たらずで解く プログラム が書けた。

Kingdom Rush

これはあっさり解けた。所要時間は 1 時間弱。

Cruise Control

未着手。コンテスト終了後に平行四辺形がたくさん出てくるグラフを紙に描きまくって解法を考えたが解けず。解説によればそんなことしなくても解けるとのこと。

Round 1B

Safety in Numbers

正しい解法にたどりつくまでに時間がかかりすぎて終了。 正解プログラム ができたのはコンテスト終了の 2 時間後。

Tide Goes In, Tide Goes Out

未着手。

Equal Sums

Small は 20 分ほどであっさり 解けた 。 Large は 500 ビットのパターンを扱うコードが C++ で即座に書けず未着手。

Round 1C

Diamond Inheritance

残り 30 分で着手。問題入力部分に 15 分くらいに時間をかけてしまう。解法自体に問題はなく Small はあっさり正解したが、 Large は std::vector でメモ行列を作るのに手間取り時間切れ (完成版 )。 Ruby で書いてたら 10 分でできた気がする。

Out of Gas

配点にだまされ最初にいちばん難しい問題に着手し 2 時間消費してしまう。例によって解法がそもそも間違っていたが Small は運よく通った。 正しいプログラム が書けたのはコンテスト終了の 3 時間後。

Box Factory

未着手。

感想

とにかく時間が足りない！の一言に尽きますが、具体的にあげると次のようになるかと思います。

• 実行速度を重視して慣れない C++ を使ったのが悪かった。 STL のリファレンスを見つつ書いてる状況なのでそりゃ時間がかかる。またいわゆる printf デバッグをするにも記述量が多くて大変だった。いつものように Ruby を使ってればだいぶましだったのではないか。

• 受験テクニック。今回は特にひどくて、無視すべき難問で時間を無駄にし、落としてはいけない問題を落としまくった。問題の見た目や配点にだまされないようにするべき。

• 実装前に正しい解法を思いつけるようにする。正しくない解法のまま実装を始めてしまうと複雑なコーディングや多大な計算量にさらに時間を奪われ苦しむことになる。これはもうセンスの問題なので、凡人は過去問をたくさん解いて修行するしかない気がする。

• 計算力を身につける。二次方程式や連立方程式を解く程度のことで手が止まらないようにする。

• 64bit にも収まらないでかい数字が出てきてもひるまないようにする。処理系の多倍長計算サポートやライブラリは使わないに越したことはないが、いざというときのために使えるようになっておきたい。

なんというかやはり Round 1 以降に必要な素養の半分くらいは、大学入試の数学の受験テクそのものな気がします。自分が高校生の頃であればもっといい線いってたんではないでしょうか (いや今度は英語がだめか)。

肝心のプログラミング能力についても、楽な業務のプログラミングだけの日々を過ごしていると基礎力は衰えていく一方だと改めて感じました。能力の維持・向上のためには日頃の勉強や鍛錬が重要なので、今後なにかチャレンジングなプロジェクトに継続的に取り組めるように生活を改造していきたいと思います。

2012/05/06 20:11:00 JST