Google Code Jam 2010 Round2 感想

撃沈。10点だけとって1550/3000位。日本人では89位だったようです。

ソースコードはこちら。

とりあえず目標のRound 2 出場は果たしたし、満足です。
……といいつつも、やっぱり欲が膨らんでしまうのが人間。
ボーダーラインの31点は、もうちょっと頑張れば手が届きそうな気がしました。
来年は Round 3 出場を目指したいですね。

2ヶ月前、私には python の知識もプログラミングコンテストの知識もほぼ皆無でした。
1ヶ月前、python は少し書けるようになりましたが、Round 1 の問題はまだ私には難問でした(今も簡単だとは思ってませんが)。
そして今、Round 2 の解説を見て理解できる程度には競技プログラミングのことを理解し、好きな言語でコーディングしろと言われて一番に出てくるのが python になりました。*1
人なんて2ヶ月あれば変われるもの、というのをあらためて実感できて本当によかったです。

何より、すごく楽しかった！
これだけ頭をフル回転させる遊びは滅多にありません。
ずっとこればかりやってるわけにはいきませんが、これからも趣味として続けていきたいですね。

また、今回も職場の仲間を誘ってみました。
去年は一人参加してくれて一緒に Round 1 まで来てくれましたが、今年はもう一人参加してくれました。
一人は予選でダメでしたが、もう一人は Round 1 に到達してくれました。
日本人の参加者約400人のうち、1%近くは自分の職場の人間というのはなかなか面白いです。
そして、とっても悔しがってくれたので非常に満足です。
自分自身もひよっこですが、こうやってプレイ人口が増えていくと楽しくなってきますね。

勉強方法メモ

今回私がどうやって勉強したかをメモしておきます。
こんな初心者の私の書いたものでも、誰かの役に立つかもしれませんので。
一応このやり方で Round 1 は突破できました。

過去問を解く

Practiceモードを見れば、たくさんの問題があります。
まずこれを解きます。
最初は何も見ずに解きます。どうせ考えてもわからないので30〜1時間ぐらいを目処に。
次に解説を読み、その上であらためて実装します。これもmax 1時間ぐらいで。
できればきちんと動くコードを書きたいところですが、慣れるまでは実装もままならないかもしれません。
ほどほどに切り上げます。
そして、Code Jam 2010 Statisticsを見に行き、自分の使っている言語でその問題を解いている人の解答を取ってきます。
まずは写経。ひたすら自分の手で書き写し、リズムを掴みます。
次に解析。一行一行読んで、どういうロジックで動いてるのかをきちんと把握します。
できれば2人ぐらいの人の解答を見たほうがいいです。同じ問題でもアプローチの仕方が違ったり、微妙なクセの違いを学ぶことができます。
最後に、数日空けてからもう一度解き直します。実装できなかったら解説や上位者のソースコードを読んで復習します。
実装できるのであれば、今度はスピードを上げて素早くコーディングできるようにします。
こんな感じの練習をひたすら2ヶ月続けました。
といっても、python でまともに解答が存在するのは Round 1までで、Round 2からは誰も解いていない問題も結構あります。
Round 2以降の問題は C++ の解答を python に移植する、という作業をしてました。
このせいもあってRound 2の勉強スピードはそれまでに比べかなり落ちましたが、それでも随分と勉強になりました。

読んで学ぶ(ネットの記事)

TopCoderのAlgorithm Tutorialsや、id:chokudai さんの itmedia での連載記事「最強最速アルゴリズマー養成講座」(一例)などを熟読しました。itmedia の記事は連載なのですが一覧になっていません。ぐぐって探してください。
実際に問題を解いてから読むと、とても勉強になります。

読んで学ぶ(本)

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

アルゴリズムイントロダクションを買いました。
図入りですごく分かりやすいです。
これ読んでひたすら基礎を勉強してました。

職場での勧誘

スパムのように、職場の興味ありそうな人たち向けに過去問解説のメールを毎日送り続けてました。
これは自分にとってもメリットのあることです。
人に説明するにはまず自分が理解していなければいけませんから、思考の整理に非常に役に立ちました。

まとめ

まあこんな感じで、別に大したことしてません。
職場の後輩には「受験勉強みたいですね」と言われました。
確かにそうかもしれません。というか勉強というのはパターン化が基本なので、どういう分野の勉強であっても基本は同じと思うのです。
本当はもっとコンテストに出場して場数を踏みたかったのですが、Topcoder は python では参加できないので、なかなか練習できる場所がありません。*2
Java や C++ で挑む人は Topcoder に参加して練習した方がいいと思います。

関連記事

• Google Code Jam 2010 Round1 感想 - 科学と非科学の迷宮
• Google Code Jam 2010 QR 感想 - 科学と非科学の迷宮
• Google Code Jam2010事前準備メモ - 科学と非科学の迷宮
• Google Code Jam 2009 1回戦敗退 - 科学と非科学の迷宮

*1:といっても業務ではまだ使ってないので本当に使い物になるかというと自信がありませんが

*2:……と思ったら、最近 codeforces という競技プログラミングのサイトができました。ここなら python も ruby も haskell までも使うことができます。