ICPCオフ会2日目
今日から本格的に活動が始まって，コンテスト1回目がありました．今日はiwiさんのチームのセットで，洗練された問題がたくさん出ました．
とりあえずその参戦記録とか．チームはid:ir5(コーダ)，id:cos65535(コーダ)，id:nojima718(ペアプロ要員)の3人．
コンテストは10:00〜15:00まで．
開始(10:00)
とりあえずAを読む．長い，よくわからん… けど，cosさんが3^nでいいとか言ってる．よくわからんけどそれっぽい．とりあえず簡単っぽいのでnojimaさんに投げてB,Cを読み進める．
しばらくしてAが通ったとのこと．
A Accepted(10:09)
それぞれの問題を検討する．Bはcosさんができそうと言っている．Cはメモ化DPでできそう?(間違ってる) というわけでcosさんがBを進めて，残りの問題をnojimaさんと僕で読み進める．
BがちょっとバグっているとのことなのでCと交代する．まぁこれは簡単…
サンプルが通らない．あれ．冷静に考えると，dfsではまずくて，bfs(というかダイクストラ)でないといけない．というかこれはDPなんかじゃなくて普通のグラフの問題．なんでこんなことしてるんだ俺，落ち着け… とりあえずBFSに書き直す．
途中でBが直りそうとのことだったのでcosさんと交代してsubmitする．WA．ウボァ．
交代．Cを進める．今まで書いた部分は中途半端に残しているが多分大丈夫だろう．
Bのバグが分かったとのことだったのでまたも交代．submitしてAC．
B Accepted(10:46 +1)
矢継ぎ早にCを投げる．TLE．え…
ダイクストラしてるだけだしどう考えてもTLEにはならないはず．もしかしてDPでやろうとしていたときの部分を中途半端に残していたのがまずかった? …ありうる．そこをコメントアウトして提出．通った．
C Accepted(10:52 +1)
残った問題について見当する．Dは経路依存性が微妙にあるのでめんどうだけど頑張ればできそうな気もする．Eは，そんなにクネクネしないんじゃね? って思ったので，できそうな気がした．Fは数論っぽいので考える必要がありそう．Gも期待値だし何かやればできそうという気がする．Iは見てなくて，H,Jはとても難しそうな印象を受ける．
cosさんがDを考えて僕がEをやることにした．
とりあえず両者がクネクネして譲るようなのは意味が無いので，どちらかは線分で結ばれているとしていい．すると，ただのダイクストラ? 簡単．適当に書いて提出．
E Accepted(11:26)
cosさんがDの解法が見えてきたとのことなのでcosさんと交代する．自分nojimaさんはその間にGを考える．
制約式を書き下すと，バネでジャンプしてからゴールにたどり着くまでの距離の期待値を変数とする関数について，不動点を見つけてやればよい，ということがなんとなく掴めた．んー，2分探索でよい? 計算量的には割と正当っぽい．
cosさんのDと僕のGとを入れ替わりながらやる．Dができたそうなので提出．AC．
D Accepted(12:27)
Gもなんか良さそうな感じになってきたので投げる．WA．えー．
途中でEとGにリジャッジが入るとのことだったので，もしかしたらGにミスがあったのではないのかと思ったけど，別にそんなことはなかった．うーむ，何がいかんのじゃ．
2分探索の上限がまずい? と思ったけど，∞=1e18くらいに設定していたので多分問題ないはず．(ワーストな場合でも500^2*1000とかそこらくらいにしかならないと思うし)
よくわかんねーなぁと思ってデバッグしていると，明らかにおかしいケースが見つかった．バネを壁とみなしてbfsするのを忘れていた… 直す．AC．
G Accepted(13:13 +1)
さて，残りは何をしよう… Fは1次元の場合が解決できれば2次元の場合もよい，というのはすぐわかるけど，1次元の場合がとても難しい．カタラン数っぽいなぁとは思うのだけど，どうすればいいんだろう…．先輩が折り返せばいいといっているけど，そうなのだろうか．
Hはちょっと考えてできそうな気がしたけど，複雑な要素がいっぱいあってとても一筋縄じゃいかない．
Iは読んでなくて，Jはそもそも謎すぎて無理ゲーにしか見えない．
うーむ，どうしよう，2人がHを考えていて，僕がFを考える，みたいな感じだったけど，何も手がつかない．あまりにどうしようもないので途方にくれていたらいつの間にか終わっていた．
Result
6ACで3位でした．東大の某2チームが8ACしていてさすがだと思います．
Gは他のチームも挑んでいたようですがどうも∞をとても大きくするのを忘れていたところが多かったらしくて，自分含めて2チームしか通っていなかったらしい．意外．
Fは，↓のように考えれば良かったらしい．うーむ，シンプルだけどすごい．自分が見たカタラン数の証明はもっと力でごりごりやる感じであまりエレガントさがなかった記憶があるのですが，これは綺麗だし次からは引き出せるようになっておきたい．
後半2時間くらい何もできなかったのがちょっと残念でしたが問題レベル的にしょうがないような気がするのであまり気にせず次からも頑張っていきたい．
