ICPCオフ会4日目

JAGによるセット．鬼畜な問題が並ぶ．

開始(10:00)

問題文を読む．英語．Aはdpっぽいけどそんなに簡単じゃない．Bはなんかよくわからないらしい．え，まじで…
C,D,...と問題文を読むが，簡単そうなのが1つも無い… なにこれ，やばくないですか．
とりあえずDがやるだけっぽいのでDをやる．適当に書いた．この時点で1時間経ってる．1時間経ってAC0だったのでかなり焦る．送る．WA．cosさんがCができそうと言っているので印刷して交代．

デバッグする．あ，x,yを間違えてる… 修正．RE．

…

RE!? いやいや，そんなはずはありえない… ちょっと，どういうことなの…
怪しい箇所らしきところがどう見ても入力に問題があるんじゃないかとしか思えない．ためしに入力がアレな感じならTLEになるコードを送る．TLE．
この時点で微妙にイラっとするけど抑える．横のチームの人が試合を放棄して(?) 床でトランプを出して遊んでいる．
とりあえずアレな入力を無視するようにする．RE．まだ直ってなかった… AC．

D Accepted(11:28 +4)

cosさんがCの続きをやる．Bがなぜか解かれている．実は普通に探索すれば間に合う? よく分からないけどもん．
Bはてきとーに実装すればいいとして，Aを考える．閉路はとりあえず縮約してやる．後は木構造についてDPしてやればよろしいはず．
Cが書きあがったげなので提出．WA．

交代してBを進める．なんか変なところで詰まって時間が掛かったけどAC．

B Accepted(12:31)

2時間半経ってるのに2ACとかでもうStandsを見るのもいやになる．
cosさんがCで簡単な方法を思いついたと言っているので交代．すぐに実装してAC．

C Accepted(12:51)

Aを適当に書く．閉路の縮約で詰まりながらも書き上げる．AC．

A Accepted(13:07)

この時点でStandsを見ると1位になっていた．1位!!!!! 興奮．
次に解けそうなものを探すがどれも難しそうで手がつけられない．Hがちょこちょこ解かれていたのでHを考える．
うーん，解かれている割には難しいように見える．線形計画問題として見て，実行可能領域が存在するかどうかを判定すればよいのでは．コードすごい短い，というかどうなんだこれは．
サンプルが通らない．というか，サンプルが解釈していた題意と違う!! 問題文をよく読む．荷物は全部まとめてぼんっと置くのではなく，1つずつ順に置いていくらしい… うわ，ぜんぜん違うじゃん…．
どうも線形計画のイメージが抜けず，解法にたどりつけない．最後のほうになって，重心は整数座標であると仮定していいし，FenwickTreeを使えばうまくできるんでは，ということに気づいたけど，時間切れになっていた．

結果

4ACで7位でした．落ちすぎ．H解けないとか痛すぎ．2時間もあったのに何やってたの．駄目すぎ．呪呪呪呪呪呪呪．
とりあえず題意の把握ミスは本当に時間の無駄なので潰したい．あとDの入力がアレなのは普通に邪悪だと思いました．
なにはともあれProblem Setterの皆様お疲れ様でした＆ありがとうございました．

Eは鬼畜物理計算＆場合わけをがんばる，Fは鬼畜幾何をがんばる，Gは謎，Iはフロー，Jは包除原理，という噂を聞きましたが解説聞いてないのであまり知りません．