ACM/ICPC Japan Domestic Contest

腹を切って死ぬべきだと思いました。
今日の順位は、基本的にyukの功績です。

直前練習

国内予選前には毎年、(Practice Sessionの他に)簡単な問題を見繕って肩慣らしに解いています。
が、今年はここで盛大に転びました。同じ O(n^2) だからと言って、より単純で非効率なアルゴリズム選んだらTLE。気持ち悪い最適化をごりごり施したのだけれど、ごく僅かに足りない。ふてくされて諦めました。
ちなみに、去年は直前練習でとても調子のよかったWatch.cが本番ではズタボロ。逆に直前練習がボロボロだったActiveJが本番では絶好調でした。直前練習の結果と本番の結果は反比例するようです。

コンテスト開始

とりあえず印刷して、yukはProblem Aに。私はBに取り掛かりました。後輩Kは今日もペアプロ担当。

Problem A: 次期町長

yukがさっくりと通しました。

Problem B: 島はいくつある？

読んだ瞬間、Red and Blackという単語が頭の中をよぎった。それどころか、パソコン甲子園でほぼ同じ問題を見た覚えがある。
B問題は冷静に考えてから書き始めないと嵌る、意地悪問題だと思ってたのに。拍子抜けだったけど、意地悪問題に弱い私にとっては大歓迎です。BFSでさくっと通しました。

Problem C: 覆面算

yukがものすごい勢いで通しました。
ここでStandingsを見たら、なんと1位。緊張してきた。

Problem D: 離散的速度

何も考えずにDijkstra。速度に加えて後戻り不能と、今までのD問題よりも若干ひねってました。
ごりごり実装 & デバッグ。Sampleが出てきたので送ってみましたが、なんとWrong Answer。
すぐにバグが見つからなかったので、先にEに行くことに。

Problem E: カードゲーム

yukがCを書いてる途中に読んでみました。最大マッチングにしか見えない。wataさんのエスパーっぷりには脱帽せざるを得ません。
yukが世界大会に持ってったライブラリからEdmonds-Karpを引っ張り出してきて通しました。

Problem D: 離散的速度 (Retry)

Eの裏でずっとバグを探していたのだけれど、まだ見つかっていなかった。
3人でデバッグを始めたら、すぐにyukがUターン禁止の条件式が間違ってることに気付いた。
直して送ったら待望のAccept! 今日のyukは輝き過ぎてる。

Problem F: 締まっていこう

毎度お馴染みのグロい幾何。でもまだ2時間も残ってるし、どうにかなると信じて突撃。
最終的には、「『紐の折れ線の連続する2本をとって、その部分のたわみを無くす』という操作を収束するまで繰り返す」という戦略に至りました。
が、バグってSampleが合わず、そのままコンテストが終了しました。

Final Standings

5問・10797秒で3位でした。
ついでにディレクトリの中身も晒してみます。

 bash-3.2$ ls -l *.cpp
 -rw-r--r-- 1 (username) student  498 Jul  3 16:35 A.cpp
 -rw-r--r-- 1 (username) student  840 Jul  3 16:43 B.cpp
 -rw-r--r-- 1 (username) student 1342 Jul  3 16:52 C.cpp
 -rw-r--r-- 1 (username) student 1642 Jul  3 17:29 D.cpp
 -rw-r--r-- 1 (username) student 2015 Jul  3 17:22 E.cpp
 -rw-r--r-- 1 (username) student 4152 Jul  3 19:30 F.cpp

Dで躓いたのが痛すぎました。タイムスタンプを見るに、最初にSubmitしたのは17:15頃。ここで一発で通していれば _(ry を倒していた & 海外派遣されてた*1と思うと残念でなりません。yukには申し訳ないことをしました。

それでもいい順位であることには変わりはないし、夏合宿にも行けるはずなので、それなりに喜んでおくことにします。
地区予選に向けて、とりあえず後輩Kを鍛えようと画策中。さて、何から教え込もうかなー。

*1:まだ無理だと決まったわけではないですが