ICPC 2003 体験記

決勝当日朝

世界決勝会場の入り口に集合している様子

 とうとう ACM/ICPC 世界決勝の日がやってきた。 昨日まではお祭り気分で過ごしていた各チームも、こころなしかみなピリピリして見える。 皆決勝に向けて準備に余念が無いようだ。 各国語で作戦会議でもしているのか、いろいろな国の言葉が飛び交う。
 我々も日本語で作戦会議.... ではなくて、緊張をほぐすために冗談でも言い合っていた気がする。

 会場に入る前に大会ディレクターの Bill Poucher さんから諸注意があった。
 会場に入っても開始の合図があるまでキーボード等、一切の機器に触ってはいけないそうだ。

"DO NOT TOUCH ANYTHING"───

選手入場

時間になったので選手達が会場に入場した。 会場はさすが Beverly Hilton Hotel である。
世界大会は警備(?)も厳しく、見物人は途中までしか入ることができない。 選手は入場する前に首からぶら下げた ID カードをチェックされ、更に大会公式 T シャツを着てはじめて入場を許可される。

デジタル機器は見物人であっても使用禁止であり、撮影も禁止である。 この写真も大会スタッフが撮った公式の写真である。 大会期間中はいたるところにカメラマンがいて写真を撮り、大会を記録していた。
写真は IBM の開発したマルチメディア情報マネージメントシステムを利用して、撮影から 1〜2 時間のうちにインターネットを通じて公開されていたのは流石である。

Bill Poucherさんが優勝トロフィーを持っている様子

 この風船つき優勝トロフィーは、もちろん優勝すると貰えるのだが、コンテストが終わるまではまだ誰のものでもないのだ。

「このトロフィーを手にするチャンスは全チームにある。」
Bill Poucher さんが言う。 彼はとってもお茶目で、
「しかーし、このトロフィーを触らないとこの大会では優勝できない。 みんなトロフィーを触るんだ!」
と言い始め、会場を一周して、みんなをトロフィーに触れさせていた。

入場して最終的な準備を行う各チーム

 辞書を机の上に配置したり、紙と鉛筆を用意したりと慌しい雰囲気が漂う。
 基本的に紙媒体のものは任意に持ち込み可能なので、机の上の配置にはそれなりに時間がかかるのだ。

大会開始に向けてカウントダウン

カウントダウン!

───スタート!

当時を振り返って

 そもそも東京大学の情報科学科から ACM/ICPC に出場して好成績を収めるというのは容易なことではない。
 まず、情報科学科は授業もレポートも山盛りで忙しく、プログラミングコンテストのために割くことのできる時間はそう多くは無いのだ。 特に ACM/ICPC が開催される 3 年生の後半には CPU/コンパイラ/浮動小数点エミュレートライブラリーなどを設計・実装するという大きな課題があり、何日も学校に泊まることを余儀なくされる人も多い。

 そういった事情もあって、我々が世界大会に向けて練習を開始することができたのは 1 ヶ月半前、しかもせいぜい週 10 時間程度しか時間をとることができなかった。 これは海外の上位チームの半分以下、トップ級チームの 1〜2 割程度である。
 例えば中国のチームなどは、世界大会のために毎日せっせと何問も過去問を解いて頑張っているらしい。

 プログラミングスキルがいくらあっても練習することなしに、決められた時間内に完全に正しく動作するソフトウェアを書き上げるのは難しい。
 ACM/ICPCプログラミングコンテストでは、ちょっとでも仕様に則っていないプログラムは間違いになってしまい、解いていないのと同じことになってしまうので、作業量の正確な見積もりやバグを起こしにくいコーディングスタイルが要求される。

などといった、普段の学校のプログラミングでは要求されない能力は、やはり訓練無しに習得することは不可能であろう。
また、英語力の点でも海外の上位チームに比べて劣っていることは否めないので、問題を読み取るスピードに関しては圧倒的に劣る。

 しかし、時間が無かったからというのを言い訳にはしたくないので、できる限りの対策は練っていったつもりである。
 今回は(今回も?)短時間ながら、ペアプログラミングなど、XP(エクストリームプログラミング)の手法を取り入れながら正確に問題を実装していく方法を練習してから当日に臨んだ。
 また、過去問を解く数を控えめにする代わりにセジウィックのアルゴリズム本に掲載されているアルゴリズムを片っ端から実装するという練習を行ったりもした。
 さらに、問題を読む速度が遅いことをカバーするために、過去の世界大会における問題を分析したりもしたのだ。

戦闘開始!

合図の風船が上がった

 いよいよ、大会の幕は切って落とされた。 ───というより大会の風船は切って上がったというべきか。

 ここからは問題についての記述が多いので、プログラミングに興味がない方は大会の臨場感を味わって欲しい。 プログラミングに興味がある方は是非、問題(英語, pdf)を見ながら読んで欲しい。

 さて、我々は事前の分析に従って開始 10 秒で問題Aを解き始めた。
 事前の分析によると、ACM/ICPC では問題Aがほぼ間違いなく一番簡単なので、我々は問題を読むことなくAを最初に解くことにしていたのだ。 一人が問題を読み、もう一人が(問題は知らないまま)データの入力部分を書く。 そしてもう一人は問題D,E,Fを読んでいた。
 ちなみに、D,E,Fを読んだのも事前の分析の結果、そう決めていたのである。 我々は、正確かつ確実な実装のためにペアプログラミングを採用していたので、最初に問題Aを解くと残りの問題を読むことができるのは 1 人しか居ない。
 我々のコーディングスピードだと、問題Aを解く間にせいぜい 1 人では 3 問しか他の問題を読めない。 また、ACM/ICPCでは易しい問題をなるべく早いタイミングで解くことが要求されているので、一番易しいことが分かっている問題Aを最初に急いで解かない選択肢はほぼないといっても良い。

 そうすると、3 問読んで、全体の中で2番目に簡単な問題を見つけるのが最善ということになるが、しかしそのようなアルゴリズムを我々は見出すことが出来なかった。
 その代わり、問題D,E,Fの中に最低1つはやさしめの問題(全体で2〜3番目に簡単な問題)があるというヒューリスティクスを採用し、決め打ちで問題D,E,Fを読み、一番簡単だと思った問題を解くことに決めていたのである。

問題A

 問題Aは一見難しそうに見えた。
 端折って説明すると、入力としては地図が与えられ、地図上には建物が配置されている。 建物を橋で繋ぐことによって全ての建物を連結したいので、その橋の数と長さを出せ、但し橋の長さの総長はなるべく短く、連結が不能なときにはできるだけ連結グループの数を少ない解を求めよ、というのが問題である。
 貪欲に(greedyに)連結をしていくと橋の長さの総計が最小になるとは一見思えないところが難しく、少し困ってしまった。 が、一番簡単な問題であるはずなので、なにか良い解法があるはずだと信じて考えていたらあっさり閃いた。

 橋を一本建てるごとに連結グループが一つ減るのだから、必要な橋の本数は連結グループから 1 を引いた数値で一定で、橋の本数は貪欲に解いても一緒である。 それならこの問題は、建物を「点」として、建物を繋ぐ橋を「辺」として、辺のコストとして橋の長さを割り振れば、グラフ理論でいうところの「最小全域木」を求める問題と等価である。
 こうして開始3分で問題の解き方が分かったので、事前の練習どおりに、Union&Find と kruskal のアルゴリズムを高速に打ち込み、多少の混乱はあったものの、無事に正解することができた。

 地方大会も経験してきて随分場慣れもしてきてはいるが、やはり最初の風船が来ると随分と安心する。
 この大会ではギャラリーにも大会の様子がわかるように、問題を 1 つ解くと解いた問題に応じた色の風船がスタッフの手によって届けられる。 ギャラリーは風船を見ながら一喜一憂し、選手達は風船を見ながら簡単な問題を捜し求めるのだ。

問題F

 さて、我々は 2 問目のターゲットとして問題D,E,Fの中からFを選んだ。
 問題Fは、4 分木によって表現された白黒画像が 2 枚与えられるので、二つの画像の AND を 4 分木で出力せよ、というものだ。

 アルゴリズム自体はさほど難しくないが、画像が4分木でエンコードされているために実装がわりと面倒である。 簡単であっても時間のかかる問題は後回しにするのが有利なこの大会である。
 しかし我々のチームの Y 君は鬼速タイピング技能の持ち主であり、プログラミングのお仕事で鍛えた実装技術はトップレベルである。
 他のチームは違う問題を解いていたようだが我々は問題Fを選択し、ごり押しだが正確かつ高速に実装・テストを終え、順調に提出。 無事解き終えることが出来た。

問題J

 さて、この間 K 君は他の問題を読んでいたが、問題Jが非常に簡単な問題であることに気が付いた。
 K 君は去年も世界大会に出ていたのだが、なんと問題Jは手を変え品を変えてはあったが、本質的には去年出た問題と同一だったのだ。
 去年の問題同様、dijkstra(ダイクストラ)法を拡張すれば簡単に解けることが分かったので早速解き始める。

 dijkstra 法はもう何度も実装しているのですぐに書き上げることが出来た。 何度も同じアルゴリズムを書くなんて無駄だと思うかもしれないが、こういったアルゴリズムは初めて実装すると冗長で複雑なコードになりがちであり、頭を整理して簡潔に記述できるようになるのも悪くはない。
 簡潔に記述できるということは、アルゴリズムをよく理解しているということでもあるからだ。 特にコンテストの場合は、タイプ数が短いことは実装時間を短縮する上でも有効である。

 この問題では、町や村があり、通行可能な町や村の間には道が存在する。 村に入るときには銀のスプーンを1つ、町に入るときには持っている銀のスプーン20こにつき1つを入村(町)料として払わなくてはならない。
 出発地・目的地と、そこへ届けたいスプーンの数が与えられたときに、最も安いルートで目的地まで行ったときに必要な銀のスプーンの数を出力せよというのが指示である。

 出発地から考えるとこの問題は非常に難しい。
 必要な個数のスプーンを届けるためには持っていくスプーンの個数を増やさなくてはならないが、持っていくスプーンの個数が増えると町に入るときにたくさんスプーンを出さなくてはならない。 初期スプーン数が増えたら、町を迂回して村を通ったほうが良いかもしれない。
 スプーンを徐々に増やしながら計算を行うと、時間がかかりすぎるので無理である。

 しかし到着地から考えるといきなり問題は簡単になる。 目的地に居る時点で持っていなくてはならないスプーンの数は当然問題で指示された数である。これを n とする。
 目的地一歩手前で必要なスプーンの数は、目的地が村なら n + 1 個、目的地が町なら約 21n/20 個である。
 こうやって後ろから必要なスプーンの個数を逆算していくと非常に計算が速くなる。 実際にはもう少し複雑で、必要なスプーン数が確定している町・村の集合を S とし、最初 S は目的地のみを要素とし、集合 S の要素へ丁度向かう道を持つ町・村に対し、必要なスプーン数を算出し、その中で一番スプーン数の少ないものを確定し、集合 S へ加える…という作業を、S に出発地が含まれるようになるまで反復する。

 dijkstra 法をご存知ない方には、この節は説明不足でわけがわからないかもしれず、大変申し訳ない。
この考え方はコンピューターサイエンスの世界では非常に有名な Dijkstra 博士が編み出した最短経路探索法である dijkstra 法を拡張したやり方で、根底にあるアイディアは同じである。
 ちなみに、Dijkstra 博士は 2002 年 8 月に 72 才で亡くなられた。 哀悼の意を表したい。

 問題Jは一発で受理された。 3 個目の風船がスタッフの手によって届けられる。
「おめでとう。」「ありがとう。」
 スタッフとの、とてもとてもささやかな会話を交わす。
 周囲を見渡してみると 4 つ風船の上がっているチームもかなりあるようだ。 しかしプログラミングに焦りは禁物。頭脳の勝負は冷静さを失ったら負けである。 あくまでマイペースを保って、目の前の問題と格闘するよう皆頑張っていた。

問題D

 次にとりかかったのが問題Dである。

 2002 年に新しい通貨、ユーロが使われるようになった。 紙幣は共通デザインであるが、コインに関しては片面だけが共通デザインでありもう片面には国ごとのデザインがある。
 この問題Dでは、いろいろなデザインのコインがユーロ圏の各国に広がっていく様子を簡単なモデルに従ってシミュレートする。 ある街に、全ての国のコインがあれば、その街は「制覇」したと定義する。ある国の全ての街が「制覇」していれば、国が「制覇」したと定義する。 また、ある街のコインは一定割合ずつ隣の街に流れる。 このとき、各国が「制覇」するまでにどれくらい時間がかかるか求めるのだ。

 この問題は素直に指示に従って、シミュレートするだけなので基本的にはごりごり実装するだけだ。
 といっても、あまりにナイーブに書いてはループ回数が多すぎて設定された計算時間を超過してしまう可能性もあるので、そのへんも考えつつ実装した。

 デバッグで多少時間を食ったが、難なくこの問題も受理されもう一つ風船が運ばれてくる。 この時点で全体の半分以上の順位に入ったことを確信した。
 アジア圏は激戦区なのでレベルの高いチームが多いが、それほど難しくない地区から勝ち上がってきたチームもあるのでコンテストの時間半分で 4 問解けばまぁ、全体の半分の順位には届くだろうと思っていた。

 しかし油断は禁物。 順位を予想している暇があったら次の問題を解くほうが良い。
 さっさと次の問題にうつる。

問題B

 お次は問題Bである。

 ライトが n 個一列にならんでいて、それらの点灯・消灯の状態が与えられている。 スイッチをひねると、そのスイッチに対応するライトの点灯・消灯状態が反転するようになっている。
 しかし、このスイッチは設計がイマイチで、スイッチに対応するライトだけではなく両隣のライトも状態が反転してしまうというのだ。
 このとき、目的の点灯状態にもっていけるかどうか、目的の点灯状態に持っていける場合はひねるスイッチを出力せよ、というのが課題である。 入出力が多倍長整数なので、その辺も多少面倒だ。

 この問題は XOR(排他的論理和) に関する連立一次方程式を解くのと等価であることは容易に理解できた。 逆に安易にそのように理解してしまったというべきかもしれない。

 最初、連立一次方程式を解くルーチンを考えて、そのように実装する方向でプログラムを書き始めていた。
 しかし、よく考えてみると3重対角成分しか 1 が存在し得ないので冗長度は 1 つしかない。 一つ目のスイッチをひねるかひねらないかで場合分けし、うまく目的の状態にもっていけるかどうかを調べるプログラムに急遽変更。
 プログラムの骨格を練り直している間に多倍長演算ルーチンを別の人が書いてなんなく完成。 サンプル入力を処理すると、目的とする答えが出力された。

 よーし、できた、と思って提出するも返答は冷たかった。

「No」

ここでちょっとブレイク

 ちょっと横道にそれて、ACM/ICPC のコンテストの仕組みについて簡単に説明しておくことにしよう。

自動判定の落とし穴

 ACM/ICPC プログラミングコンテストはシビアである。 プログラムが正しいかどうかの判定はコンピュータによって基本的に自動で行われるからだ。
 審判団は予めプログラムの入力とそれに対する正しい出力を何種類か作っておく。 この入力と出力データは選手たちには秘密である。

 我々選手が作ったプログラムは提出されると同時に、ネットワークを介して審判コンピュータへ転送され、審判コンピュータ上で実行される。 コンピューターは予め審判団が作った秘密の入力データをプログラムに与え、出力が期待されるものと同一であるかをチェックするのだ。
 そして、結果が正しいものと同一であれば「Yes」、正しくなければ「No」、定められた計算時間を超過しても計算が終わらなければ、「Time Limit Exceeded」という返事をチームに返す。

 審判団による手動の判定も同時に行われるが、プログラムが正しいか正しくないかをリアルタイムで判断するのは人間にはとうてい無理である。 実質審判団は不正のチェックをするくらいの仕事をすることとなる。

 これは何を意味するかというと、プログラムが間違っていてもどこが間違っているのかはさっぱり分からないということだ。
 プログラムに与えられる入力データは秘密になっていて、選手達には分からない。 1 箇所でも間違っているプログラムは受理されず、しかも、受理されない問題はそもそも解いていないのと同じなのだ。

 たとえば、ゲーム会社の開発現場で間違ったプログラミングをした事態を想定してみよう。
 あなたはロールプレイングゲームを開発中で、さっき、武器屋でアイテムを購入する部分を実装し、テスト部隊へプログラムを回したところだ。 すると、テスト部隊から、
「ねぇねぇ。このゲーム、主人公の所持金が足りなくても武器屋で剣を買えちゃうんだけど、バグじゃない?」
と、具体的な症状とともに開発現場にフィードバックがある。
 あなたはそれを受けてプログラムを修正し、お金が無いときには武器が買えないようにプログラムすることができる。

 ところがこのゲーム会社を ACM/ICPC 方式にしてみると、次のようになってしまう。
 あなたはロールプレイングゲームを開発中で、さっき、武器屋でアイテムを購入する部分を実装し、テスト部隊へプログラムを回したところだ。 すると、テスト部隊からメッセージがくる。
「No」
 あなたはプログラムが間違っていることは分かったが、なにが間違っているのかはさっぱり分からない。 アイテムを購入したときにそのアイテムを主人公の持ち物に追加するのを忘れたのか、それとも所持金を更新しわすれたのか、買ったアイテムと違うアイテムを持ち物に追加してしまったのか。プログラムの各所をチェックしていくがどうも正しいように見える。
 つのる苛立ち、過ぎる時間.... そして、プログラムは修正されないまま納期を迎える。
 ACM/ICPC 方式では、誤りのあるプログラムは無いのと同じである。 あなたはお客からも冷徹に宣告を受ける。
「あなたのプログラムは間違っていますね。受け取れません。」

ペアプログラミングのススメ

 そういうわけで、我々はペアプログラミングを採用していた。
 最近の流行といえばそうなのだが、実際、ある程度大規模なプログラムを組むときにはペアプログラミングは非常に有効な手法であり、コンテストに限らず、開発の現場でも有用であると徐々に認識され始めている。

 ペアプログラミングは文字通りペアでプログラミングを行う手法である。
 一人がコードを書き、もう一人はそれをサポートする。 傍目にはサポート役の人はサボっているようにも見えるかもしれないが、実際にはサポート役の方が重要である。

 実際にプログラムを書いている人は、サポート役の人に内容を説明しつつコードを書く。
 他人に説明できないようなアルゴリズムは要するに自分でも分かっていないのでそのまま書いてもバグを生む。 しかし、説明をすると一旦頭の中で整理がつくので、バグを生みにくい。
 また、サポート役はコードを見ながらバグを見つけたり、よりよい実装を提案したりする。 見ていてじれったくなったら役割を交代するのが原則だ。

 2 人で書くと、別々に作業するのに比べて半分の速度になるのが心配? そんな貴方はコーディングよりデバッグに時間を掛けていませんか? 1 人で書いて、つまらない思い込みや見落としのせいで延々とデバッグをした経験はありませんか?
 慣れるまでは数十時間かかるかもしれませんが、慣れたら、「書いたら書いただけプログラムが動く」世界に、片足を踏み入れることが出来るかもしれません。

閑話休題

 そして大会は、いよいよ後半戦へと突入する…。

ACM PROGRAMMING CONTENST