アジア地区予選東京大会参加記 - にゃあさんの戯言日記

アジア地区予選東京大会が終わった。結果から書くと、2位。1位は京都大学echizen.batだった。

とりあえず、東大内では1位で世界大会に進むための必要条件(ただし十分ではない)はクリアしたと思われるのでかなり良い結果。ただ、終了1分前まではトップだったようなので、最後に逆転されてしまったのがちょっとだけ残念。

以下、長めの参加記が続くので興味のある方だけどうぞ。

チーム紹介

東大のチームUnknownのメンバの一人として参加。チームメンバは、ush, nya, kzk の三人。コーチはchunさん。

ush: Algorithmist. ひたすらアルゴリズムを考える担当。競技時間中はほとんどずっと紙に向かっている。できたアルゴリズムは全員に解説して、クリアに伝わったなら私とkzkさんでペアプロ、数学的考察が必要だったり複雑なものならushさん自身がペアについてコーディングをすることになる。
nya: Coder. ひたすらコーディングする担当。競技時間中はほとんどずっとキーボードを叩いている。アルゴリズムができている問題が無い時だけはアルゴリズムを考えるけど、普段はずっと実装。
kzk: Commander. 他の二人のサポートをしつつ、チーム戦略を進める担当。ushさんと一緒にアルゴリズムを考えたり、私と一緒にペアプログラミングをしたり、問題を解く順番の決定(スケジューリング)をしたりと、やることが一番多いポジション。作業に没頭しやすい他の二人から少し離れた位置で、チームとしてのマネジメントをやってくれる。
chun: Coach. 過去にGNC(ryとして世界大会に出場された経験のある方。海外遠征の手配などの事務処理をそつなくこなしてくれる。精神面でのサポートにかなりお世話になっています。

1日目 (11/2 金曜日)

この日は平日なので普通に授業がある。レジストレーションに間に合わないと困るので途中で演習を抜け出して代々木オリンピックセンターへ。演習はぶっちしてしまった必修の授業なので出席がちょっとやばい... もう二度と休めないなあ。台北大会も金曜に被っているけど、その週の金曜は祝日らしいので助かった。交渉してないのでもしかしたらちゃんと話せば公欠扱いにしてくれるのかもしれないけど面倒（ぉ。

会場に到着すると既にレジストレーションが始まっていた。チームメンバ3人はすぐ揃ったけど、まだコーチが来ていなかったので、来るまでホールで待つことに。その間に__________やTalesOfCodersの人たちが来て会場に入っていき、ホールで待っている東大チームはうちらとMakegumiのみになった。この２チームのコーチはよく予定時間ギリギリに現れることで有名なので、どちらのコーチが先に現れるかということでプチ競争をしたのだけど、ここは私たちの敗北。にょろーん。

ちゅんさんが到着して会場入り。代々木オリンピックセンターはACM/ICPC OB-OG会合宿で何度も訪れていて、あの施設に50チームを収容する部屋なんてあったかなあ... と心配だったけど、案外に悪くない環境だった。快適というわけではないけど不便もないので問題なし。

しばらくしてトライアルユース(計算機環境に慣れるセッション)が始まった。自分的には、とりあえず与えられたキーボードに慣れるのがこの時間の一番の目的。自分は普段はHHKB Proを愛用していて、バッククォートやバックスラッシュ、エスケープの位置が一般的なASCII配列キーボードと違う配列に慣れているので、本番でつまづかないように練習。持ち込んだチームライブラリのコードをひたすら写して、400〜500行くらいを入力してみた。結果的に、場所が違うのはあまり打つ頻度が多くないキーがほとんどなのであまり問題なさそうだった。むしろ問題はキーが重いことか... プログラマはキーボードが命なんだから、もうちょっと品質の良いキーボードを用意してくれてもいいのにな。

トライアルユースが終わり、センター内の宿泊場所に荷物を置いた後、レセプションホールで立食形式のウェルカムパーティ。このパーティのメインはチーム紹介で、毎年ある意味でクォリティの高い紹介が多いのが日本大会の特徴(他の地域の大会に参加したことはないんだけど)。今年は普段どおりのサブカルチャーネタに加えて、ニコニコ動画ネタが目立ったような気がする。中国のチームまでがスライドに「うｐ主自重」とか流していて日本チームは騒然。向こうの人たちも見てるんだなあ。

一番秀逸だったチーム紹介はTalesOfCodersだったと思う。内容を口で説明するのは難しいけど、ymatsuさんのテンションの高いスピーチと秀逸なスライド絵*1。のおかげで会場の全員が引き込まれていた。初参加であのクォリティを出せるのはすごい。
ちなみに我らがチームの紹介はすごく普通だった。来年はもうちょっとどうにかしようと思う。

ウェルカムパーティの後は宿舎に戻って翌日に備えるのみ。とりあえず風呂に入って、談話室で他のチームとしばらく話をして、11時頃にみんなそれぞれの部屋(今回は全員個室)に戻って就寝。
...のはずだったんだけど、眠れない。最初、1年のときに愛媛大会に参加したときはそれほどよく眠れなかった記憶があるけど、今回はそんなレベルじゃないほどに眠れない。
今回は去年までと違って、東大からのチームの実力がかなり近い位置にあって、どこが世界大会枠を獲得してもおかしくない状況だったからかもしれない。チャンスは今までに参加してきた大会の中で一番大きい、けどそれを逃す確率も高い。もともとプレッシャーにはかなり弱い方だし。

そんなわけで、今回はコンディションとしては最悪な、睡眠時間30分という状況で本番に臨むことになってしまった。

2日目 (土曜日) 本番前

この日は7時に起床して朝食を取り、9時半から競技スタート。といっても寝たのは6時半なんだけど...

ちゅんさんに朝食後もスタートぎりぎりまで寝るように言われたけど、結局眠れず。でも、眠れないほどの緊張は仮眠の後もずっと続いていたので、途中で眠くなることはないな、というのが希望的な予想だった。

コンテスト本番

スタートと同時に、ぼくは環境設定とサンプル入出力のダウンロード。他のふたりが問題を読みにかかった。

セットアップが終わったところで、ushさんが読んでいたB(Prime Gap)が簡単なことが発覚。ぼくとkzkさんでペアプロを始めて、数分で特にバグもなくプログラムが完成。Accepted.

次に、ushさんがA(And Then There Was One)の内容を解説してくれた。いわゆるJosephus数といわれているもので、効率よく計算する方法があるらしいのだけど、実際にはナイーブに計算しても時間的に間に合う。最初は答えが合わなかったものの、すぐに修正して完成。Accepted.

この辺で一度ネタが尽きたので、少し問題を読み進めることに。問題文が短めなC, D, E, F, Iあたりを読んで、C(Minimal Backgammon)が簡単そうということで、問題を読んだushさんとコーディングを開始。これは一発で答えがあって、そのままAccepted.

次に出来そうなのを考えていたところ、F(Slim Span)がKruskal法の変形で解けそうなことが分かったので、kzkさんと一緒にライブラリを使いつつ実装。これも一発で答えが合い、Accepted.

この時点でHを除く問題は読み終わっていた。とりあえず、G(The Morning after Halloween)の状態数があまり多くないのでmemoized BFSができそうなことが分かったのでkzkさんとコーディング開始。しかし、ushさんが読み終わったH(Bug Hunt)のほうが速く書けそうだと言って、さらに周りを見たところHは既に解かれているようだったので、急遽そちらにスイッチ。最初、答えが合わなかったものの三人がかりのデバッグで10分ほどで解決。Accepted.

その後途中まで書いていたG(The Morning after Halloween)を再開。実行したところ、なぜかプログラムが暴走してメモリを食い尽くしたらしく、kill -9するまで数分間まともに操作ができなかった。原因はfreopenのミス... 今後のためにエラーチェックを追加して、気を取り直して再実行。最初はghost同士がぶつかる条件を書くのを忘れていて結果が合わなかったが、すぐに気付いてそこだけを修正したら答えがあった。しかし実行時間がちょっと長く、サンプルインプットの最後のケースを処理するのに16秒かかっていた。総ケース数は10でタイムリミットが180秒なのでなんとかなりそうだが、ちょっと怖い。若干の高速化をすると6秒になったのでそこでsubmit. 問題なくAccepted.

既にushさんがI(Most Distant Point from the Sea)のアルゴリズムを出してくれていたので、ushさんとペアプロを開始。間違えないように二人で確認しあいながらアルゴリズムと数式をコーディングして実行してみたところ、最後のサンプルケースでNaNが出てきてしまった。誤差きついなあ... EPSを1.0e-8に修正したのとlong doubleを使用するように変更して対処。Accepted.

ここで少し休憩することにして、昼食をとった。あまり食べ過ぎても眠くなると困るので、おにぎりを一個。

残るはD, E, J. E(Geometric Map)はどうみても線分アレンジメントが全ての実装問題。D, Jは謎。とりあえず方針の立つEをやりはじめることにして、ぼくとkzkさんでコーディング、ushさんが残りの２問を考える体勢になった。
線分アレンジメントはライブラリに入っていなくて、実はそれが気になっていて木曜の夜に書こうかと思っていたのだけど、結局書かず仕舞いだった。これで解けなかったらかなり悔しいことになるので意地でも書き上げようと思い、二人で確認しつつひたすら実装。木曜に実装しようかどうか迷っていたときに他のチームのライブラリをみて大体の方針は確認していたので、そこで詰まることはなかったのが救いだった。最初は間違っていたのだけど、assert()でひっかかってくれたおかげですぐに原因が分かり、そこを直したところサンプルが一致。提出、Accepted.

残るはD(Lowest Pyramid)とJ(The Teacher's Side of Math)の2問。Dはある程度方針は立ったもののコーナーケースがそれなりにありそうなのと、計算時間が掴みづらいという感触。Jは線形連立方程式に落ちるはずなので、次に解くならこっちということになった。
この時点で8問解いているチームはうちだけで、しかもここまでペナルティを一度も食らっていないため、時間は問題なし。残り時間は約1時間。これはあと1問解けば勝てそうだと思ったので、三人でJに取り掛かることにした。

Jは線形連立方程式なのだけど、条件がかなり特殊で、解が整数になることが分かっているらしい。ただし、途中計算の数値は有理数になりうる。ここで、64bit整数を使った分数を使えば範囲に収まるという仮定をおいてコーディングスタート。トリプロのかいがあって書き上げることができたものの、どうやらサンプルの最後のケースでオーバーフローしている... これは多倍長整数がないとどうにもならないと思い、急遽JavaにスイッチしてBigIntegerを使うという方針に変更。しかしJavaは書きなれていないので、コンパイルは終了5分ほど前に通ったもののバグが取れず、そこで終了。実は分数を使う必要はなくて、浮動小数で十分ということに気付いたのは終了後数分のことだった...

2日目 (土曜日) 本番後

アワードセレモニー。順位発表があり、最後の1分でDを通したechizen.batが1位。Unknownはそれに続いて2位。3位は~~北京大のA New Start~~Makegumi. (追記: ごめんなさい間違えてました)
日本で開かれた地区予選はこれで10回目だけど、1位を日本チームが取ったのは今回が初めてだったらしい。すばらしい。
表彰式のあとはなぜかBINGO大会。OB/OG会のひとがはっちゃけていた。あと、このセレモニーにはスポンサー企業の人たちやジャッジの方たちも来ていて、知り合いの方々といろいろ話したりした。

その後、さらにいわゆる"裏ICPC"もしくは"sake challenge"に参加。年々規模が大きくなっていて、今年は参加者が60人を超えたらしい。よく収容できたなあ... 内容は、まあ、とりあえずみんな自重してなかった。

宿舎に帰ったらすぐにベッドに倒れこんで死んだように眠りについた。

感想

横浜大会のちょっと後から新しいチームで練習してきて、1年弱でこれだけの成績を残せるようになったのは本当にすごいと思う。特にushさんとkzkさんはICPCにはそれまで出たことがなかったのに、初参加でここまで来られると1年の頃からやってきた自分が恥ずかしい程ですらある。
コーダとしての自分は、速さはそれほど悪くないけど、正確さがいまいちだと思っている。今回はしかもほとんど徹夜状態で、もし一人でコーディングしていたら悲惨な結果になっていただろう。しかしこんな最悪な条件下で、ほとんどバグを出さずにはまることなく実装していけたのは、二人のサポートがあってこそだと思う。本当に二人には感謝してもしきれない。ありがとう。

おそらくMakegumiは海外派遣先のベトナムで勝ってくると思うので、事前の取り決めどおりプレーオフで世界大会に進むチームを決めることになると思う。だから、まだ世界大会へ行けるかどうかは分からない。でも、このチームなら大丈夫だと思う。