ICPC国内予選2008参加記
チームWARushとして参加してきました。Warushとは北アイルランドに位置する羊毛と角笛の生産が盛んな地域です。風光明媚です。嘘です。
練習セッション
てけとーに書いて送る。横のチームが一生懸命問題送信用スクリプトをmechで書いていた。それを見て先輩がICPCにおける送信用スクリプトの歴史について語っているのを横で聞く。参考になる(5)。練習セッションが終わる頃になるとチームメイト二人がいなくなる。試験があるらしい。試験時間は丁度練習セッションが終わる時間から本番が始まる時間までなのでちょっと不安である。
本番
他のチームメイトが来ないよー。周りの人に「AとかBなら一人でもどうにかなるよ！」って励まされる。そうかも。でも追い打ちをかけるように開始時間になっても問題文が読めない。5分位経っても読めない。計算機室は張りつめすぎて変な空気に。「読めないよー」「読めた所ありますか？」「読めません」「これサーバは東大だよな」「東大は読めてるのかな」「東大チームの強さにはそんな秘密が」などとみんな話している。素晴らしい洞察(5)。むしろ前日から問題文を入手しているんじゃないかって位強いからな東大は。
しばらく経つと後ろのチームが問題を読み込めたらしく静かになる。俺はまだ読めない。あせる。俺も横で問題を読もうかと思ったが恥ずかしいので止めた。早く早くーーー読めた！
A
太郎と花子がカードを交換する問題。始めに和を出してー差を取ってーとか考えたがカードが100枚しか無いので全通りシミュレートする事にした。がりがりがり。書いてる途中にチームメイトが一人やってくる。待ってたze！Bを読んで下さい！がりがり。特につまる事無くsubmit & AC。
B
チームメイトに説明してもらう。でも聞いてもわからないので問題文を読む。月曜土曜数？月曜土曜素数？明らかにミスリーディングを誘う文章。読めない。うーん。月曜土曜素数で因数分解すれば良いのかな？適当に書く。サンプルと合わない。サンプルの数字が大きすぎて検算が面倒。合ってるはずなのにな〜合わないなーと思ってチームメイトに相談すると全然因数分解の問題ではない事が判明。与えられた数を割り切る月曜土曜素数を出力する問題だったらしい。話を聞かないでごめんなさい。問題説明の時に月曜土曜素数を始めに生成した方が良いって言ってたのはこの事だったのか〜。急遽プログラムを書き換えて実行するとサンプルと一致。わーい、送信！AC。
C
Bをやってる最中に二人目のチームメイトが来ていて問題文を一通り読んでくれていた。早い。とても頼りになる。Bが終わった時点でCとDのどっちを先にやるか相談する。Dが問題文中の画像から明らさまに幅優先探索or順位優先探索（ダイクストラ）だったのでやりたくなるも、Cは構文解析を書いて27回ループするだけで簡単そうだったのでCをやる。ちゃちゃっと書いてコンパイルするもコンパイルエラー。なぜ？簡単な事しか書いてないよ？原因が全然わからない。negateとmultを上の方で定義してあるのに、下の方で使おうとするとgccが「定義されてませーん」エラーを吐く。なんでなんで。5分くらい色々試して、仕方ないのでnegate関数とmult関数を手動インライン展開。すると普通にコンパイル出来てサンプルも一致。送信。AC。謎だなーと思うも忘れて次に進む。終わった後に調べてみると関数名として使ったnegateとmultが実は定義済みだった事が判明。ひどい。。ここらへんでBとCに多少無駄な時間を割いてしまったとの思いから、不安になるのでstandingは終わるまで見ない事を決意。
D
Cが何事も無く通ったのでDに着手。始めにロボットに命令を出さずに止まるまでシミュレートして通過したマスをコスト0にしてからほにゃらら？とか、普通の幅優先探索でいける？とかいう話になったが、命令ごとにコストが違うのでダイクストラでないといけないという事になる。おお、ダイクストラ！うまい！嬉々として書き上げました。っていうか去年もDはダイクストラだったよなー、つるつるロッククライミング問題。去年はあれを解いた時点で学内１位が決定したんだったな。などと思いつつコーディング。チームメイトに「これで良いんですよね？」「ですよね？」と聞きまくりながら書く。去年は自分はコーダーのサポートをしていて、終わった後に「助かりました！」って言われても全然助けた気になれなかったのだが、自分がコードを書く側に回ってみるとサポートしてもらうと本当に助かる。脳みそが2coreになったみたいだ。問題内容としては、各ノードから全部の命令に対応する枝を伸ばして、もしその命令がマップ上に書かれた命令と一致するならばコストは0になり、そうでないならば命令に対応するコストが加算される。終了条件としてif (here.r == H && here.c == W)と書いていてバグってた（正しくはif (here.r == H - 1 && here.c == W - 1)）以外は特に問題はなく、サンプルと一致。送信するとACが帰ってきた。ここまでで一時間半くらい。
E
残ったEとFのうちどちらをやるか相談。Fは同型判定がめんどくさそう。Maximum Cup Winterに出たテトリス問題を思い出し萎える。かと言ってEはなぁ。。幾何だし。。とこちらも去年の幾何を思い出し躊躇。しかし説明を受けるとEは比較的手が届きそうだったのでこちらを選択。
問題の説明を受けて議論。空間幾何？直線と平面の距離？とか悩むが平面幾何に落とし込めそう。幾何ライブラリを写経する間に数学的な計算を紙でしてもらう。最初はコースの直線と直方体の4点との距離から円の半径を計算していてサンプルが合わなかった。３０分ほど悩んで直線と直線の距離だ！という事にチームメイトが気付き修正。サンプルが合う。おぉ！5問いける！提出。どきどき。WA。なぜ。そこから10分ほど誤差関係をいじくり4回ほど送信するが無情にもWA。そのままタイムアップ。結果は4問でした。
結果
全体8位学内2位で予選通過できました。素直に嬉しいです。4問しか解けませんでしたがWAをRushしなかったのでこの順位でした。学内1位チームは5問解いて偉い。東大チームは6問解き過ぎだ！
終わった後に先輩に「どの順番で解いたの？」と聞かれたので「ABCD(E)でーす」って答えたら「普通ですね」って言われた。確かに。俺もキテレツな順番で解いてみたい。学内1位チームはABDCEだったみたい。DとCの順番はチームによって変動ありそうだ。もっともうちのチームがDCの順で解いていたらペナルティが増えてもっと順位が下がっていた事でしょう。
今回は3人で解く大切さが身に沁みて分かりました。Eなんて殆ど言われるままコーディングしただけです（終了後にEは些細なミスでWAだった事が判明。幾何の解釈に問題は無かった）。コーダーがコーディングを頑張る事で他の二人は問題読解に全力を注げる。他の二人が問題を読む事でコーダーはコーディングに全力を注げる。計算機が一つだなんて事はほんの些細な問題でしかありません。
終了後は自由が丘のモーパラで打ち上げ。先輩にFの解法を説明してもらい、Eを選択したのは正解だったなぁと思いつつすき焼き鍋で卵焼きを作ってあきれられる。食べてくれた人はありがとう。みなさんお疲れさまでした。
