ICPC 2012 国内予選

ICPC

++(w++というチーム名で出場していました。
3位に入れました。
スタンディングとかは以下のような感じです。
http://www.psg.cs.titech.ac.jp/icpc/icpc2012/common/guest_standings_en.php
http://imoz.jp/icpc/2012-domestic.html

当日の流れを忘れないうちにおおまかに書いておこうと思います。


なんとなくサイコロが出るような気がしたので、当日の午前にAOJのVirtual Contest中に書いた回転関係のコードを印刷してました。
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=518のD問題のやつです。


会場が駒場なのでお昼ごろ移動して、ついたあとはプラクティスで3問解いて、現地環境に慣れました。来年はプリンタとかPCとかの持ち込みを本気で考えました。
始まるまではスタンディングは落ち着くまでは見ないようにしようみたいなことを喋ったり、直前にテンプレの打ち込み練習をしたりしていました。

16:30開始
先輩にコピー機まで走ってもらい、その間に別の先輩にテンプレを打ち込んでもらい、自分はディスプレイに表示されたA問題を読んでいました。
いきなり日付関係だったので、少し焦りながらコーディングを開始しました。
全日付が初日から何番目かをもっておけば大丈夫そうだったので、前計算させて引き算しました。
日付遷移が多少バグって焦りましたが、先輩がB書けそうと言っている横で少し時間くださいとかなんとか言いながら、書き上げてサンプル通ったので投げました。
AC


先輩にB問題を打ち込んでもらう間にもう一人の先輩にC問題の概要と解法を聞いて、サイコロだったのでB問題が書かれているあいだにライブラリの確認と、実装の方針を練っていました。
途中Mac環境でCAPSLOCKキーが入ってしまい、直し方が分からずにやむなく再起動しました。本当にこのことを想定していなかったのが痛すぎました。(コンテスト終了後にCAPSLOCKの直し方を他チームの方に教えてもらいました。

再起動した後はするすると書き上げてもらってすぐにAC出来たと思います。

そして、Cの実装にとりかかりました。
方針としては、まずサイコロの全ての面の状態が知りたかったので、それをサイコロ転がして前計算させるコードを書き、
そのあとで、降ってくるサイコロの動きをシミュレーションさせました。
問題の説明を受けている間はいろいろと気をつけるよう言われていたことが打ち込んでいるあいだに抜け落ちてしまい、４から６の面にしか回転しないとか、大きい方に転がるとか、そのた様々なバグを埋め込んでしまってサンプルが全然通らないので、Eが書けるとか言われて幾何担当の先輩にPCを譲り、印刷してデバッグを始めました。
何度かPCを交代してもらいながら３箇所くらい修正したらやっとサンプルが通ったので、それを投げたら無事通りました。

自分がCの実装とデバッグをしている間に、先輩二人にD問題の解法を考えてもらっていたので、概要と解法を教えてもらって、２０分くらいで書けると言われたので、E問題を書いてもらっているあいだにFとGについてもついでに説明してもらいました。
(スタンディングを見るとCをACしてから本当に20分くらいで通っていておどろきました)

そうしているうちにEのサンプルが通ったので、桁数に気をつけて提出してもらうとACをもらえたので、Dにとりかかり始めました。
そのあいだに先輩二人にはF、Gを考えてもらっていました。

先輩によるとDはまず会社ごとに全点間の距離とそれに対するコストを求めて、一番安い経路でグラフを作りなおしてダイクストラすればいいと言われたので、その方針で行きました。
一番安い経路を計算するところがかなりバグってしまい、先輩に助けを借りながらなんとか直してACをもらいました。

ここまできて、F,Gが解法の糸口があまり見えてこないので取り敢えずスタンディングを見ると3位に入っていたので落ち着いていけば大丈夫だと思いながらFかGを通そうと3人で考え始めました。

ちょっと考えたところFはいろいろと考えないといけないことが多く見え、Gのほうは最大マッチングっぽい問題に落とせそうだったのでGが解けるかもしれないとそっちにシフトしました。
しかし、結局嘘解法を実装している間に嘘かもしれないということになり、簡単に書けそうなほうに方針を転換しましたが、残り10分くらいだったので、頑張って書いてましたが、バグってサンプルが通らずにもう無理だということになり、残り30秒くらいは祈りながら必死にスタンディングスをリロードしまくってました。
終了後あっさりとバグが見つかり、5分ぐらいで直せたので(あっているかは自信ないのですが)CやDのバグとかCAPSLOCKがすぐに解除できればサブミットくらいは出来てたのになと思うと少し悔しく感じました。

結局3位に入ることができ、何も問題なければ無事にアジア地区予選に出場することができそうです。合宿などにも初めて呼ばれるかもしれないので、非常に楽しみに待ちたいと思います。
今回の国内予選は上2つは順当な感じでしたが、東大内3位は本当にどこがなってもおかしくない感じだったので、うちのチームがとれて本当に良かったです。

最後の問題は結局提出できませんでしたが、チーム戦であーでもないこーでもないと相談しながら戦うのは本当に楽しいですね。
去年と違って今年はVirtual Arenaで週3くらいのペースでチームとして練習しまくっていたのでチームワークがかなり鍛えられたことも大きかったと思います。
来年は他のチームも赤い人が出現しそうでとても怖いですが、それまでにこっちも誰か一人は赤くなっていることを祈ります。頑張ります。

二人の頼りになる先輩に感謝。