2006 TopCoder Open - Algorithm Competition の決勝戦が行われました。オンライン・ラウンドを勝ち抜けた 48 人が、ラスベガス・アラジンホテルに招待されオンサイトで 5/3-5/5 の 3 日間にわたり戦いを繰り広げました。最後に勝ち残った 8 名による決勝戦の模様は通常の TopCoder のアリーナ上でリアルタイムで見ることができました。といっても、ライブ映像が流れていたわけではなくて、こんな感じで
競技者が行っている「問題を Open」「コンパイル」「テスト」「コードを提出」等の行動をリアルタイムで知ることができたわけです。問題の内容や各競技者が提出したコードもリアルタイムで見ることができました。アリーナ上では見学者が集まって、それを見ながら「あーだこーだ」いって楽しんでいます。
Final に残ったのは以下の 8 名。
蒼々たる面子です。。ホスト国の 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 は
と基本的なアルゴリズムの組み合わせって感じですね。見事です。。。