ACM/ICPC 2004-2005 参加記 -- アジア予選マニラ大会

文責:稲葉 一浩

Introduction

2004年11月20日から11月22日の三日間にわたって、 ACM/ICPC2004年アジア地区予選大会が 愛媛大学で開催されました。以下は、我々 チームGokuri-Squeeze がコンテストに参加した際の レポートである。

※ Gokuri-Squeezeは同年のマニラ予選大会で世界大会出場権を既に手にしていたため、 愛媛大会には、順位の付かないオープン参加という形で参加しました。 この形での参加許可を下さった大会実行委員の皆様に、この場にて感謝いたします。

Before

コンテスト前日、あやうく出発時間に遅れそうになって駆け込んだ飛行機に乗って、 Gokuri-Squeezeは決戦の地、愛媛に降り立った。空港で会った同じACM/ICPCの参加者と合流して、 歩いて愛媛大学に向かう。

到着すると、英語での受付を済ませて(ICPCでの"公用語"は英語となっている。 アジア地区予選以上では、問題文の記述やアナウンスなど、全て英語で行われるのだ。)、 練習セッションを早速開始。

Gokuri-Squeeze のメンバー達

この時間は、『与えられた数のうち最大のものを返せ』などの 簡単な問題を解いてみることで、コンテスト本番の環境やシステムに 慣れることを目的に設けられている。しかし、こういう練習時間には、 ついつい簡単な問題を無駄に大道具を持ち出して解いて遊びた くなってしまうのもプログラマの性。ひとしきり無駄に大がかりなソースを 書いて練習問題に答えて遊んでいたGokuri-Squeezeであった。

歓迎会

練習セッションが終わると、歓迎会が始まる。明日の大会に向けた軽い緊張は、 各チームの工夫をこらした素敵な自己紹介で思わずなごんでしまう。 強烈な一発ネタをかますチーム、大学の名所を紹介して皆の感嘆を誘うチーム、 明日のライバル達のそれぞれの持ち味が見えて楽しい会なのだ。

さて、大会当日の朝は早い。早めに休んで、決戦の朝を迎える。 練習セッションとはどこか違った空気の中、用意されたTシャツに袖を通し、 端末の前に座る。カウントダウン…5…4…3…2…1………スタート!

Contest

※ 以下のレポートでは、Gokuri-Squeezeが問題に取り組んだ過程を順番に記載しました。 プログラミングの腕に覚えのある方は、是非 公開されている問題データ を見て考えてみながら臨場感を味わって下さい。

問題A

Gokuri-Squeezeは基本戦略として「二人がペアプログラミングで端末に向かい、 残りの一人は横で問題を読んだり考えたりする」という人数配分でICPCに挑んでいる。 端末で取り組んでいる問題が解けたとき・解けそうもないと判明したとき・ 脇でにらんでいる問題が実は一瞬で解ける簡単問題だとわかったときなどに、 適宜、役割の入れ替えをしていく。何度もの練習での経験から、特に開幕直後は いつも吉野&川中ペアが第一問目、問題Aに取りかかり、稲葉が残りの問題を読みにかかる、 という分担に落ち着いた。

さて、というわけで、今回もまずは問題Aに挑戦。

問題Aは、『天秤が1個と、重さa,重さbの2種類の重りがたくさん 用意されているとき、使う重りの個数をできるだけ少なくしながら重さdを計れ』 というもの。数式で考えてみると、ax+by=d になるような数x,yのうち、 できるだけ小さいものを見つけてくればいいことになる。 これは "拡張ユークリッド互除法" だ! 早速、持参のGokuriライブラリノートに 収録済みのコードを打ち込みにかかる。

拡張互除法では最適なxとyが見つかるとは限らないので、実際には、 最初に得たxとyを調整して、一番重りの個数が小さくなる解を見つける必要がある。 その計算をするプログラムを完成させて、問題文に書かれいるSample Inputを入力…… あれ?Sample Outputと合わない…?

少し修正を加えてみてもやはりダメ…なんと、いきなり問題Aでつまずいてしまった。

問題C

こういう時は、一旦別の問題に席をゆずって、ゆっくり考え直すに限る。 バトンタッチ先として選んだのが問題C。『ある暗号アルゴリズムがあるのだが、 実はあまりできがよくなくて機械的に解読できてしまう。解読プログラムを書いてみよう』 という内容だ。問題を読んだ稲葉曰く、「これ簡単、答えが問題文に書いてある」 とのことで、実際、問題文中の、解読できてしまうことの説明が実は そのまま解読プログラムの書き方説明になっているのだ。

ささっと書き上げてSample Inputで試して…あれ?またしてもダメ!?

問題Aに続いて少し焦ったが、Sampleと結果が違うのは、よく見ると、 最上位bitの立った16進整数が入力として来ている部分のみ。 さては入力データの読み取りに使ったstrtol関数は、 符号付き32bit整数で表せる範囲の数しかパーズしてくれないのでは? と睨んで修正。修正と言っても、一文字増やしてstrtollに変えて64bit符号付き整数まで 対応できるように拡張したのみだが、今度はSample Outputと合う結果が無事帰ってきた。 バンザイ!Submit!Accepted!

風船

余談になるが、例年問題Aは一番簡単な問題が配置されていることが多いため、 我々に限らず、まず問題Aから取りかかるチームは多い。このため、 毎年会場に真っ先にあがるのは、問題Aの赤い風船なのだ。

コンテスト終了後の雑談で、Gokuriから最初にオレンジの風船が上ったのは意外だった、 と他のチームの人たちを驚かせることができたことを知ってニヤリ… と行きたいところであったが、実際は我々も普通に問題Aを解くつもりでいたのに できなかったというオチなのであった。

問題E

さて、コンテストに戻って、次に簡単そうと判断したのが問題E。 『与えられたたくさんの文字列のうち、まぎらわしいペアを全部出力せよ』というもの。 「まぎらわしい」の定義は問題文中に厳密に指定されていて、 一文字置き換えるとか一文字削除といった基本操作を2回繰り返すと 一致してしまうものがまぎらわしいとされる。

「定義は書いてあるんだからその通り探索すれば簡単じゃない?」ということで、 各文字列に可能な操作2回をほどこして他と一致するかどうかを片っ端から試してみる というコードを書いてSubmitしたところ…審判の返答は"Time Limit Exceeded"。 そんな方法では遅すぎるということだ。残念。

問題D

問題Eは、小手先の技は考えついても抜本的な改革は思いつかなかったので、さらに問題スイッチ。今度の候補は問題D『URL風のパス文字列が2個与えられたとき、同じ位置を指すかどうか判定せよ』。パス中の .. で上の階層へ上ることができるとか、最後の / の後ろを省略すると index.html が補完されるといった細かい条件が面倒そうだが、つい先日のマニラ大会でも同じようにパス文字列を扱う問題を解いていたため、慣れでなんとかなるだろう、と判断。

この問題もひたすら指示通りに実装するのみ。Sample Inputでのチェックも通ったが、ここは慎重に、自分たちでいくつかテストデータを作って検証してみることにする。案の定、バグを発見!しっかりつぶしてからSubmit。Accepted!

テスト駆動

また余談になるが、本体よりも先にテストコードを作成して、テストを通るかどうか常に検証しながらプログラムを開発する "Test First" という開発方法が有効であることはよく知られている。もちろんACM/ICPCにおいても、テストはバグ削減に非常に大きな効果をもたらす。……だが、ICPCでは、コーディング時間は数時間と限られているという特殊な事情がある。そこで、どこまで厳密なテストをするか、それとも割り切ってSubmitして時間の短縮を図るか、悩むところなのである。

問題A再び

問題Dを終えるとここで、しばらく横で平行してバグ取り作業を進めていた問題Aに戻って完成させることにする。今度は正しく動作するようだ。Accpeted!

周りを見渡すと、AやEで詰まった分、いささか遅れをとってしまったようだ。この遅れを取り戻すべく、残りの問題をじっくり見比べて確実に早く解ける問題を潰していかなくては。残る問題は6問。どう攻略していくか、しばらく検討会議することになった。

この中で、見た瞬間解くのをあきらめたのが、問題I。元々平面でも図形問題はどちらかというと不得手なのに加えて、立体図形ということでお手上げていた。問題Hも同じ理由で難易度高めに見えていたが、これは出てくる図形は球だけだし、やれば解けそうな気もする問題に分類。

逆に、これは行ける!と判断したのが問題Bと問題G。問題が一般化されると難易度があがるが、指定された問題サイズ(Bは3x3x3固定、Gは国の数は10個まで)が非常に小さいので、特別な工夫をしなくても答えが出せるはず。問題Fも、やってみると実は探索すべき空間はかなり狭いのでは?と予想はしたが、とっさに確証は得られなかったため一時保留となった。

問題B・問題G

というわけで、だんご三兄弟に取りかかる。指定された手順をシミュレートして、三個同じ色が並んでいるかどうかの勝敗判定をするのみ。Accepted!

さらに地図の塗り分け問題Gへ。最大で10しか国がないのなら、1色で塗ってみる→塗れたら1を返す、2色で塗ってみる→塗れたら2を返す、…、10色で塗ってみる→塗れたら10を返す。というバカ探索で十分間に合うはずと確信して、さっくりとコードを書いてしまう。Accepted!

問題…

さて、残り時間は1時間程度。一度取りかかってしまったのでなんとかしたい問題Eと、なんとかなりそうな気がする問題Hにターゲットを絞ることにする。

しかし、基本方針はそのままで様々な枝狩りで挑んだ問題Eは、"Time Limit Exceeded"→"Time Limit Exceeded"と、なかなか制限時間に及ばず。画期的に速くなって帰ってきた!と思いきや"Wrong Answer"。やっぱり根本的に方針を変えなきゃだめらしいと考え直し、最後の砦問題Hにとりかかるも…

Time up!

After

コンテストが終わると、参加者皆で松山城ツアーへ。コンテストの興奮醒めやらぬ中、他のチームと「IterativeDeepningが…」とか「数値積分で…」などと、お互いの解き方について語り合う少し不思議な一団。

さて、舞台は表彰会場のホテルへ。いよいよ、最終結果の発表だ。

優勝は…上海交通大学Spiritチームの9問中8問正解!コンテスト中の風船をあげるスピードでも圧倒的な強さを見せつけたSpiritチームが断トツのトップであった。おめでとう!

一方我々Gokuri-Squeezeの最終結果は、9問中5問正解。公式の順位はつかない形での参加だったのだが、トップのSpiritの8問!や、2位の京都大学Combatチームの7問と比べると、だいぶ見劣りのする結果となってしまった。今回の反省を生かして、世界大会での両チームとの対決にはぜひとも勝ちを収めたいものである。

Conclusion

こうして愛媛大会は幕を閉じた。

次の ACM/ICPC 2005 アジア地区予選は、2005年7月の予選を経て、11月に東京工科大学で開催される。このレポートをごらんの貴方も、チームメイトを募って、参加してみてはいかがだろうか…?

Copyright © 2005- Team Gokuri-Squeeze (gokuri _AT_ isers _DOT_ jp)