2006 TopCoder Open - Algorithm Competition の決勝戦が行われました。オンライン・ラウンドを勝ち抜けた 48 人が、ラスベガス・アラジンホテルに招待されオンサイトで 5/3-5/5 の 3 日間にわたり戦いを繰り広げました。最後に勝ち残った 8 名による決勝戦の模様は通常の TopCoder のアリーナ上でリアルタイムで見ることができました。といっても、ライブ映像が流れていたわけではなくて、こんな感じで

競技者が行っている「問題を Open」「コンパイル」「テスト」「コードを提出」等の行動をリアルタイムで知ることができたわけです。問題の内容や各競技者が提出したコードもリアルタイムで見ることができました。アリーナ上では見学者が集まって、それを見ながら「あーだこーだ」いって楽しんでいます。

Final に残ったのは以下の 8 名。

• tomek : ポーランド・Purdue 大学。現在 TopCoder でレーティングトップ。優勝候補の最右翼。
• Petr : ロシア・モスクワ大学。TopCoder では珍しい C#使い。数々のプログラミングコンテストで名を残しているそうです。Google Code Jam 2005 でも 3 位に入っています。いつも綺麗な読みやすいコードを書いてくれるので、参考になります。
• misof : スロバキア・Comenius 大学。
• John Dethridge: オーストラリア・メルボルン大学。
• andrewzta: ロシア。
• cyfra: ポーランド・ワルシャワ大学。
• natori : 上位陣には珍しい Java 使い。日本人です。
• fuwenjie: 中国・TsingHua 大学。

蒼々たる面子です。。ホスト国の US 勢はひとりも Final に残れなかったのか。。問題セットは Final にふさわしく通常の SRM よりもはるかに難しいものばかりそろっています。

実況開始！

250 点問題は比較的容易だったらしく、ほとんどの競技者はそれほど苦労せずに Submit。 500 点問題も fuwenjie, Petr, tomek と続々と Submit。こんな感じでリアルタイムに問題と提出されたコードを見ることができました。

優勝するには 1000 点問題を解く必要がある雰囲気が漂いはじめました。そんな中残り時間 26 分で tomek が 1000 点問題を提出！

この時点でトップに立ちます。

Petr が続きます。

Petr 人気者です。「go Petr!!!」

見学者たちは、「tomek の 1000 点理解できねー。」「tomek のは greedy algorithm だ」「Petr のはよさそうだ」とわいわいチャットしてました。

Petr の 1k(1000 点問題）を見てみましたが、binary search を使用しています。。。この問題から binary search を思いつくとは。。その発想がすごい。。そうこういってるうちに、なんと natori が 1k を提出！

Petr 残り 5 分というところで、500 点問題を再提出。。

コーディング・フェーズ終了。現時点での順位はこのとおり。natori がトップ。tomek、Petr が続きます。

チャレンジ・フェーズ

5 分間の休憩後、チャレンジ・フェーズの始まりです。 Petr 開始直後に立て続けに 500 点問題で 3 つ撃破！！いっきょにもりあがります。

tomek と natori の 1k も撃墜されました。チャレンジ・フェーズ終了時点で Petr がトップにたちます。

いよいよ、あとはシステム・テストの結果まちです。。。。

結果

見事、Petr が栄冠に輝きました。賞金 2 万ドル Get です。。おめでとう！！結局 1k に正解したのは Petr だけでしたね。Petr の 1k は

• Binary Search
• Sort してから Greedy
• union-find

と基本的なアルゴリズムの組み合わせって感じですね。見事です。。。