ICPC練習会

模擬練習会があった。
今日も二人だったけど、今日はちゃんと集まってやった。
キーボードも英語キーボードでやった。

結果は、とりあえず一位だったが、どうにもすっきりしない。
というか、こんなんじゃ駄目だ・・・。
最後のほう、完全にぐだぐだだったし。

まず、練習フェーズ。
いつもどおりさくっとトップを確保。
で、最後の解けない問題をがんばる。
きっと何か元ネタがあるんだろうなぁ、と思いつつ、
結局解けなかった。まぁ、これは当たり前というか。

それから本番。
開始と同時にA問題を解きにかかる。
とりあえずA問題に対して言うことはない…。
10分ほどで完成。普通にアクセプト。

次、B問題。
問題のサイズが小さいから全探索してしまいました。
で、終了ー、と思いきや……
なんと、Wrong Answerをくらう。このとき開始28分ほど。
なんでかなあ〜〜と思いつつ、微修正して再送するも駄目。
で、10分ほど経過。今日はもう駄目かなぁ…と思いながら
メールボックスを見てみると、
「問題Bの審判側のテストデータに誤りが発見され、現在修正されました。」
とかいうメールが来ていた。
おいおいおいおいおいおい。なんじゃそりゃ？
とりあえず再送、アクセプト。
こんな問題に30分も食ってしまった。

自明な問題は終わっちゃったらしい。
どれにしようかと思っていると、M氏がFの回答を思いついたようだ。
問題Fはn人の人がn分割された地図を持っていて、
都合のいい日に会いながら誰か一人のもとに全部地図を集めるのにかかる
最短の日数を求める問題。
これは各々がその時点で持てる可能性のある地図をマージしながら計算すると
簡単に答えが求まる。
要するに、地図はコピー可能で、みんなにコピーを配ると考えると分かりやすい。
解き方が分かると実装は簡単である。
さくっと実装。さくっと送信。さくっとアクセプト。
とりあえず簡単なほう3問を一時間で処理できた。

次、どれをするか。
M氏はDは幾何だから手を付けにくいとかいっていたが、
どうもそんなことが無いような気がして、Dを解くことになった。
Dは正方形と直線がいくつかあって、
直線によって正方形がいくつに分割されるか、という問題。
三本以上の直線が同一点上で交わらないときの平面の分割は有名な問題だが、
それのちょっとした変形だ。
直線を加えたときに、領域の数は、
(正方形の上で交わる交点の数+1)づつ増加する。
幾何問題なのでM氏が書くということになった。
で、私は残りの問題を考えることに。

残りは問題Cと問題E。
問題Cは魔王の瘴気から逃げながら勇者がクリスタルを集めるというような問題。
(て、よく分かりませんな…)
問題Eはややこしい郵便配達の問題。
問題Cは解けるような気がしたんだけど、
色々考えているとやっぱりよく分からなくなってくる。
最も悩んだのは、クリスタルへ向かうときに直線じゃなくて、
瘴気を迂回するようなルートをとるべき場合があるかということ。
これが分からなくて、結局書けば通りそうな問題Eをよく読むことにした。

そうこうしている内に30分経過。問題Dが解ける。
で、あらかじめ考えておいた問題Eを解き始めることにした。
問題Eは、まず各郵便局から郵便局へ配達するときの
次の中継地点を求める必要がある。
最初読んだときはなんとなくダイクストラ？とか思っていたが、
ダイクストラでは駄目っぽい。
経路の逆から探索しないとだめだなぁ、どうするか。

と思っていると、横でCを考えていたM氏が
瘴気を迂回するルートが存在し得ないことを証明した。
そうと分かれば問題Cにチェンジである。
直線の移動しかないとすると、問題のサイズも20までなので、
深さ優先探索すれば答えは求まりそうである。
どういう順番でクリスタルを回収していくかを探索するが、
枝刈りをしないと20までといえど無理っぽかったので、
探索の全時点において、残りのクリスタルに到達不可能なものが出たら
探索を打ち切る、というようなものを入れた。
で、実行。なんかおかしいぐらい早く実行が終わった。
それから回答送信。Wrong Answerを食らう。
なんでかなぁ…と思ってソースを見ていると
探索のところでクリスタルの回収したフラグの扱いがおかしくなっていた。
これだから副作用は嫌いなんだ。
とりあえず修正。実行。今度は3秒ぐらい実行に時間がかかった。
再送。アクセプト。この時点で残り1時間弱。

さて、最後の問題である。
問題読めば読むほどややこしい問題だということがわかってきて、
正直残り一時間弱ではどうなんだろうなぁ。
とおもいつつ、とりあえず書かなきゃ駄目だろということで。
方針は、中継地点テーブル作成=>シミュレーション、だ。
中継地点のテーブルは逆ダイクストラとでも言うべき方法で華麗に作成。
…と行きたい所だったが、もうめちゃくちゃ時間がかかった。
最近こういうコードを全然書いていなかったので時間のかかることかかること。
結局20分ぐらいかかって完成。
サンプルと照合、合ってそう。
残り30分強。正直無理だろうなぁ、と思いつつ。
シミュレーションはイベントドリブンな感じでごりごり書いていく。
で、書いていくはいいんだが…。
規則がめちゃくちゃ複雑なのである。
同じ時刻に来た荷物はあて先の番号が若いものから、とか、
郵便配達の人は同じところに持っていく荷物が複数合ったらまとめて持っていくとか、
出力は到着時刻順、時刻が同じならアルファベット順、とか。

混乱しながら、コードも二転三転しながらコーディング。
で、結局書いている途中に時間が来てしまった。
しかし、ここまで書いてというのも悔しいし、
もしかしたら事故の補正でちょっとぐらい遅れたやつでもアクセプトしてくれるかも、
という淡い希望を抱きつつ作成継続。
結局12分オーバーで完成。
とりあえずサブミットしたが、コンテストは終わりました、という返事であった…。

そういうわけで、なんとも煮え切らない結果であった。
4問ぐらい時からトップかな？と意識していたのだが、
_oopチームがぴったり付けてきてたのは不気味だった。
時間差で勝てるかな、とは思ってはいたが、なんともかんとも。
あと、補正が3000秒ぐらいということであるが、
二回不正解(2400秒)+(実際にアクセプトされた時間-最初に正解を送った時間)なんだろうけど、
実際のところ、10分ぐらい足止めされたわけで、それ以降に正解した問題全問から
(実際にアクセプトされた時間-最初に正解を送った時間)を引いた上で、
試合時間をその分延長してもらうぐらいしてもらわないと割が合わないと思った。

というわけで、なんだか長くなったが、
こういう機会を与えてもらったことはありがたいと思います。
良い練習になったので、本番でもいい成績が取れるといいなぁ。

・おまけ

スコア
なんとなく、採取してみたので。