ICPC国内予選レポート
昨日行われたACM/ICPC 国内予選大会のレポートです。
開始前
この日は1限から授業が入っていたので、7時半くらいに起きた。前日は早く寝るつもりだったのが、なんだかんだやっているうちに遅くなってしまったので眠い。それでもなんとか授業には間に合った。が、授業開始20分後に睡魔に負けて、意識を取り戻したのが授業の終了5分前。金曜日の授業は1限しか入っていないので、あとはICPC国内予選に臨むだけになった。
2限は同じクラスのetoと情報棟でまったりして過ごす。昼休みにはチームメンバーのtoyo,YAMAが揃ったので、練習セッションにとりかかった。特に何事も無く終了して、本番開始の一時間前になるまで一度解散。ぼくは昼ごはんを食べてなかったので生協で食事をとってきて、時間になるまでずっと情報棟の会場でぼーっとして過ごす。この頃から緊張が高まってくる。
本番開始一時間前に全員が集合。同じ教室では駒場チームのnaebaとsodan、本郷チームのwhile1forkとGNCが参加。本郷チームはECCS(情報棟のシステム)のアカウントを持っていない人が多いので、ノートパソコンを持ち込んで、同じ階にある田中研究室から引っ張ってきたLANケーブルでインターネットに接続したみたいだ。田中研究室から会場の中演習室３まではかなりの距離がある(30〜40m?)のでリピータを使って何本ものケーブルを繋いでいた。あんなに長いLANケーブルは初めて見た。
準備が終わってコンテストが始まるのを待つだけになると、緊張がピークに。
本番
午後4時30分、ついに本番がスタートした。とりあえず問題を印刷。ちなみに日本語版のほう(あとでこの事をSHNSKさんに言ったらヘタレって言われた(笑))。AをYAMA、B,Cをtoyo、Dを僕が読んだ。とりあえずCが一番簡単そうだということだったので、最近切り込み担当になっているらしい僕がとりかかる。問題は、或るちょっと変わったフォーマットで表記された整数が二つ与えられるので、その二つの和をとって同じフォーマットで出力せよという問題。そのフォーマットと整数の間の変換関数を作ってしまえばおしまいなのでさくっと仕上げて、0:20にAccept。
次にYAMAがAにとりかかる。問題文が長いだけで、ちゃんと条件どおりにプログラムを書けばいいだけの問題。0:33にAccept。
Aのコーディング中、僕はBを考えた。最初、端点から線分の長さと曲がる方向を使って正規化しようかと考えていたけど、toyoが両端点について0,90,180,270度の回転をさせたものとマッチさせるだけで十分だと教えてくれたので、その方針で書いた。そのおかげでだいぶコーディングが楽になって、0:52にAccept。
残りはD,E,F。Eは明らかに面倒そうだったのでD,Fを解く事に。その時点で、Dはダイクストラをちょっと変形したアルゴリズム、Fは掃除ポイント間の距離を求めてグラフに落とした後深さ優先探索で解けると考えていた。Dは8種類のチケットの使用状況を表す数の処理が面倒そうだったりしてちょっと時間がかかりそうだったので、Dの解法を二人に話してFに取り掛かった。
Fは前述の解法でコーディングして、1:23にAccept。Dを二人に託して僕はEの方針を考えることにした。
ここまでのペースがそこそこ良かったので、自分の中の予定としてはDを2:10くらいまでにAcceptさせて、残りの50分を最後のEに費やそうと思っていた。多分50分あってもデバッグが間に合わないだろうな、とは思っていたけども。しかし2:15頃にコンパイルが通ったと思ったら、リンカでエラーが出るというトラブルが発生した。実は、4*(256*30)^2 = 225MBのところを間違って数MBと計算してしまって、これくらいなら隣接行列作ってもいいじゃん、ということで
> int cost[256][30][256][30];
なんていう恐ろしいグローバル変数を定義していたのだった。
しょうがないので、リスタートして隣接行列を使わないバージョンをコーディング開始。この間にwhile1forkが5問目を解いて我らが_oopは学内4位になっていたので、かなりのプレッシャーがかかった… 色々とエンバグしつつもなんとか書き上げて、2:49、Accept。学内3位に。残り10分でEを書くのは絶対無理だと分かっていたので、あとはタイムアップまで祈りながら待つことにした。
その時4位だったIHI Mastersが時間内にもう一問解けば負け。解けないか、一回でもrejectを食らえばこちらの勝ち。どっちに転ぶか全く分からない中の10分間は本当に長かった…
そして午後7時30分、タイムアップ。結局IHI Mastersは4問のままで、_oopは学内3位で予選を通過したのでした。
感想
そんなわけで、最後は他のチームに追いつかれないことを祈るしかないというちょっと苦しい状態になってしまって、それがちょっと後味の悪さになってしまった感じ。でも、問題Dのトラブルを除けばあとは全て順調に進められたので、全体を通してみれば十分良かったと思う。
しかし、三廻部さんが仰っているように、今回の問題セットは、解法は割と思いつきやすい問題が多かったように思う。僕らのチームはそういう問題セットはそれなりに高速に解けるのだけど、解法が難しく分かりづらくなってくるに従って急激にパフォーマンスが落ちることが分かっているので、地区予選までにもっと練習を積まないと、去年の愛媛大会のようになってしまうだろうなぁ…
ちなみに「本番」の所には書かなかったけれど、実は午後6時にECCSの端末が全て電源を落とされるというハプニングが起こった。会場になっていた教室が普段は6時までしか使われない教室で、時間になると自動的にシステムが落ちるようになっていたらしい。復旧するまでの約５分間は紙デバッグに切り替えてなんとかしのいだけど、さすがにあれはびっくりした。
追記
金子先生に教えて頂いた情報。
int cost[256][30][256][30];
の問題は、心静かに
int (*cost)[30][256][30] = new int[256][30][256][30];
とすると、それだけで通った可能性もあったかも。
実際に該当箇所をそう変更してみると、まだデバッグ中のコードだったので正しい答えは出ませんでしたが、問題なく実行できました。…がーん。
