ICPC 2003 体験記

後半戦

 前半戦に戻るにはこちらから。

風船 lighthouse の面々

 風船も続々と上がってきた。 ちょうど半分を過ぎ、簡単な問題をみなそろそろ解き終えたであろう、この時間からこそが、大会の正念場である…。

大会に戻って。

問題B再び

 さて、コンテストに戻って、再び問題B。

 問題Bのプログラムにはなにやら間違いがあるらしい。 しかし、問題文に印刷されているサンプルの入力に対しては正しい出力を返しているし、ペアプログラミングで、コードレビューをしながら書いてきたので、大枠は間違っていないことを確信していた我々は正しく動作しない例を探し始めた。
 様々なありうる入力データのうち、性質が変わる点や境界付近(例えば水の温度だったら、0 度・100 度付近で処理を変えたりしそうなので、-1 度・0 度・1 度・50 度・99 度・100 度・101 度で正しくプログラムが動作したら全ての入力温度に対してプログラムは正しく動作しそうだ。)を考え、入力データ数 n が小さいときにバグがある可能性が高いと予想して、n = 1, 2, 3 のテストデータを作って処理させた。

 案の定 n=2 のときの処理が間違っていて、誤った出力が出ていた。 面倒なのでアドホックではあるが、n=2 のときだけ特別に処理して正しい答えが出るように修正し、提出。 受理された。
 そして新しい風船がやってきた。

さて、残る問題はどうしよう

 ここで我々は一旦作戦会議を開いた。
 簡単な問題はあらかた解き尽くしたと思われ、ここからは問題の選択が運命を左右する。
 間違って難しい問題を引いてしまったら最後、長くて複雑なプログラムを頑張って書こうとした挙句の果てに、コンテスト終了までにプログラムを完成させられないかもしれないからだ。

 A,B,D,F,Jはすでに解き終えた。
 Cは Z-カーブ上での2点間の距離、というものが簡単に計算できれば解ける問題だった。 少々検討したが Z-カーブ構造を上手く扱う計算方法が思いつかず見送ったほうが良いだろうという話になった。
 Eは穴と直方グリッド(格子)上のポリゴン(多角形)が与えられ、ポリゴンが穴を塞ぎ得るかどうかを調べる問題。 ありうる平行移動をしらみつぶしに生成し、実際に平行移動させて穴を塞いでいるかチェックすれば解けるが、実行速度的に大丈夫か自信が持てなかったのでパスすることに。
 Gはいわゆる「リンカー」と呼ばれるプログラムを作成する問題。 ちょっと指示が長いが、悩むところもそれほど無いし、タイプ速度が速い我々のチームには良さそうである。
 Hは電車網と時刻表が与えられたときに指定の駅・時刻まで「駅での待ち時間が最も少ない」経路を求める問題である。 これも DP (Dynamic Programming, 動的計画法)で解ける。
 Iはたくさん風船が上がっているのできっとそこそこ簡単なのだろうと踏んで解くことに決定。

問題G

 さて、問題記述が長いGではあったが、頑張って読んで、すぐにコードを書き始める。

「リンカー」は、最近は知っている人も少なくなったが、簡単に言えば、プログラムを部分ごとに分けて書いたときに、それを最後に結合するのに必要なプログラムのことを言う。 (正確には、プログラムをコンパイルすると、オブジェクトファイルが生成され、そのオブジェクトファイルを結合するのがリンカーである。)
 昔からプログラミングをしている人にとっては馴染みの深いプログラムなのである。

 各オブジェクトファイルにはシンボルがあり、各シンボルにはそのモジュール先頭からのオフセットアドレスが付加されている。
 モジュールを連結して各シンボルのアドレスを確定させたのち、そのシンボルを利用している部分に書き込む。

 時間はまだ約2時間残っていた。 刻々と時が過ぎる中、我々は黙々とコードを実装していった。
 これくらいの時間帯になると、たいていのチームが動かないプログラムを抱えていてデバッグのために相談を始める。 テーブル同士は十分離れているので何を話しているのかは分からない。 もちろん聞こえたとしてもたいていは英語以外の言語なので意味は分かるはずも無いのだが、コンテスト開始直後の静寂と比べると、会場全体が微かにざわめいている雰囲気が感じられた。

 さて、実装は終わったつもりだったのだが、問題文に印刷されているサンプル入力に対して正しい出力を吐いてくれなかった。 原因はすぐには分からなかったので問題Iにスイッチした。

問題I

 この問題は簡潔で、Kepler の第三法則を利用して指定した時間における惑星の位置を求めるというもの。
 ただし、計算してみると方程式がややこしく、これを解析的に解くのは難しい。 とくれば、当然コンピューターの力を使って数値的に解くわけである。

 方程式の数値解法といえばまずは Newton 法というわけで、最初は Newton 法で惑星の位置を求めることを考えてみた。 方程式を f(x)=0 とおいて、f(x) は目的の区間で単調である、というところまでは順調だったのだが、問題文に指定されている解の精度を達成するために必要な反復の条件が上手く絞り込めない。
 そこで、f(x)の単調性を利用して二分法で解く事に。 二分法の場合には解の精度は区間の大きさそのものであり、必要な反復回数も非常に簡単に見積もることができる。

 こうして問題Iは問題Gがハマっている間に必要な式・プログラミングを全て終え、あとはうちこむだけという状態になっていたので、さっさと打ち込んで提出した。
 これは一発で受理され6つ目の風船をゲット。

問題G再び

 残りは 1 時間と 10 分ほど。 これくらいになってくると時間との戦いである。

 丹念にソースをチェックしていったところ、チェックサムの定義が通常と異なり、ビットシフトではなく、ローテイトで計算しなくてはならないのを見落としていたことに気づく。
 その点を修正すると問題文のサンプル入力に対して正しい出力を吐き出すプログラムになった。

 やった。 これで7問目が解ければかなりの上位に食い込める可能性が出てくる───
 まだ1時間以上時間が余っている───
 1時間あればもう1問解けるかもしれない───
 8問解ければベスト3も夢ではない───
 いろいろな考えが頭を駆け巡る。 しかし妄想に浸るのは3秒で止めにして次に問題Hを解くための方法について思いを巡らし始めていた。

問題G、そして焦り

 しかし、その思いはあっさり裏切られてしまった。 提出したプログラムに対し帰ってきた返事は「No」。
「え?嘘?」と思って内心動揺したが、30 秒で冷静に戻る。

 ここからの時間の経過は早かった。 問題文の指示を守っているか片っ端からチェック、しかし特に問題のあるコードは見つからない。
 境界条件付近のテストケースを作ってみるも正常に動作しているように見受けられる。

 ひょっとして問題の指示を勘違いしているのだろうか? ソースコードを印刷して並列でチェックをする。

 無情にも時間は 10 分、20 分、と過ぎていく。
 そんな中隣の清華大学のテーブルから喚声が上がり、選手達が手を叩くのが聞こえてきた。 どうやら問題が解けたらしい。

Last 10 seconds

 そうこうしている間に、残り時間は 10 秒となった。 全チーム観念したらしく、最後の 10 秒は全チームでカウントダウンを行う。

"Ten, Nine, Eight, Six, ....,"
"Three"

"Two"

"One...."

 割れるような拍手と共に、大会ディレクターの Bill Poucher さんはコンテストの終了を宣言した。

その後

 コンテストは終わった。 解きかけで 1 問残ってしまったのは残念だが、あの状況下でできることはやったと思う。
 5 時間、頭をフル回転させてきた我々は、サンドイッチとジュースを頬張りながら体を休め、表彰式を待った。

表彰式

表彰式で喋る Bill Poucherさん

 解いた問題数と時間はコンピュータによって集計されているため、大会が終わって数時間で結果が出る。 そして夕方になり、表彰式がはじまった。
まずは、大会運営に携わったボランティアの方々を紹介することからである。 大会を支えてきた人たちを壇上に呼び、感謝の意を表するのだ。 プログラミングコンテストの中では言うまでも無く最大の規模を誇るコンテストを運営するには、多くのスタッフの労力を必要としたことは言うまでも無い。
彼/彼女らの活躍には心から敬意を表したい。

正装..??!

途中、時節柄アカデミー賞のパロディで、こんな姿で登場するスタッフ達。 燕尾服に蝶ネクタイ.....である。誰がなんと言おうと。

結果発表

 そして、とうとう順位の発表が始まった。
 上位 12 チームに 1 チームも入っていない地域は、地域チャンピオンのみの発表となる。 アフリカ・中東地域のチャンピオン、ケープタウン大学、南太平洋地域チャンピオン、ニューサウスウェールズ大学、そして、ラテンアメリカチャンピオン、全体の 12 位がブエノスアイレス大学だ。

ブエノスアイレス大学

 年々女性の参加者は増えているが、トップ 12 チームに入ったのはおそらく彼女が初めてではないだろうか。
 一人目立つ格好をしていたのもあり、彼女、ジュリアーナさんは皆の視線を釘づけにしていた。 話によると最近は後輩のプログラミングスキルを鍛えているらしい。

 そして..... 11 位は我々のチーム、東京大学!

東京大学 team lighthouse

 年々大会のレベルが上がっている上に、12 位以内は壇上に登れておまけに賞金まで出るので、このへんのランクの争いは本当に熾烈で、まず入れないと思っていたので、名前を呼ばれた瞬間嬉しくて頬が緩みっぱなしになってしまった。
 カメラを東工大の知り合いに預けて慌てて壇上へと向かう。 銅メダルと賞品と、そして、とびっきりの "Congratulations!" という言葉に心からの "Thank you!" を返して、壇上で会場を見渡す。
 明るい壇上から照明が落とされた室内はよく見えなかったが、そんなことはどうでもよかった。

 10 位は Albert Einstein University Ulm で、同じく 6 問だが速度で上回った。
 9 位は Taras Schevchenko Kiev National University で 6 問を解いた。 ここまでが銅メダルである。
 8 位は中国の新設大学、Zhongshan University。

 7 位に Saratov State University (ロシア)が 7 問を解いてランクイン。
 6 位には去年優勝した Shanghai JiaoTong University (上海交通大学)が入った。
 5 位はTsinghua University (清華大学)、ここは常連である。 彼らは 7 問を解いて、アジアチャンピオンとなった。
 中国は世界大会に 4 チーム送り出しただけでなく、5, 6, 8, 13 位を占め、今年も実力を発揮していた。

清華大

 つづいて金メダルのチームの発表である。
 4 位は Comenius University。
 3 位は St. Petersburg Institute of Fine Mechanics and Optics であった。 ここまでが 7 問。
 7 問も解いて 3 位という結果は、今年のレベルの高さをうかがわせる。

 2 位が Moscow State University、8 問。
 これを聴いて我々は「あれっ?」と思った。 彼らは 8 つの風船をなびかせてトップを走っていたので、誰もが優勝だと思っていたのだが…。

───そして。

ワルシャワ大学

 優勝はポーランドの Warsaw University。 なんと、9 問も解いたとのことである。
 5 時間、つまり 300 分で 9 問を解くには問題読み・コーディング・デバッグ・提出作業込みで 1 問あたり 33 分。 ここまでくるともはや実力だけでなく、運も必要な領域なのではないか。
 彼らは優勝を確信していて、スーツ姿で壇上に現れた。 彼らには全く脱帽である。

 そして、大会開始前に皆が集まった、あの優勝トロフィーが、彼らに手渡された。

Top12

終幕

 こうしてコンテストは終了し、我々は翌朝早くに帰国の途についた。 戦争も始まっていたので、今回は観光は無しである。

 我々は幸いにして 1 万人以上の参加者が居る世界的コンテストにおいて、世界 11 位を勝ち取ることが出来た。 が、当然次は更なる高みを狙いたくなるのが人情というものであろう。
 しかし、この願いは来年以降の人たちに託すことにする。

 来年壇上に立っているのは、ひょっとして貴方かもしれない....

ACM PROGRAMMING CONTENST