ICPC2011 国内予選
haskell-lover というチームで参加していた．メンバーは俺と id:osa_k と id:draftcode．
結果は全体で10位，学内で1位になれました．
http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/common/guest_standings_ja.php
http://imoz.jp/icpc/2011-domestic.html
基本的には模擬国内予選のときみたいに
- draftcode が C からどんどん問題を読んで，解き方を考えてもらう
- osa_k が A を考えて書いて，D を考えてもらう
- eagletmt が B, C を考えて書く
で，それ以降はよしなにやる，というかんじの予定だった．
A
いつも通りやるだけなので osa_k に適当に書いてもらう．
B
どう見てもやるだけだったのでそのまま osa_k に書いてもらう．
C
すべてのマスについて色を変更できると勘違いしてやや重いかと思ったけど，電極が左上のマスに固定されているということを指摘されて，これなら全通り試せばいいだけで実装も簡単っぽい．
やや実行速度が遅かったが，書いてほぼ一発でサンプルと最初のインプットが通った．
しかし2回目のインプットに対してまさかの WA．コーナーケースも思いつかないし，アウトプットを眺めてみてもそんなに変な値は入っていないっぽい．
そこでふと提出するときに誤ってインプットを送っていたかもしれない*1ことに気付いて，注意しながら提出し直したら AC．
提出ミスにすぐ思い当たって本当によかった…
すみませんすみません…と3つめのアウトプットも送って AC．
D
解けるという話だったので osa_k に任せて E 以降を見ることにする．
E
draftcode から説明を受けてやることはだいたいわかったけど解法がわからない…
F
やることは明快で幾何ゲーっぽい．これはがんばって実装すればいけるのでは(←まちがい)
G
任意の一箇所のドアが壊れていてそのときの各最短経路の最大を求めるだけかと最初勘違いして，30x30 だしまさかやるだけ？と思ったが，ちゃんと読み直すと解釈が違っていることに気付いた．
うーん…
だいたいこのあたりで osa_k が D を通し終えていた．
問題を軽く説明した後，E を osa_k と draftcode が考えて，F を俺が考えることにした．
F
図を書き散らしながら，方針を考えつつ場合分けが必要な場面を列挙していく．
まず杭(原点)と建物の各4点の角度でソートして，右から処理しつつできる弧の軌跡の長さと，左から同様に処理してできる弧の軌跡の長さを足す，という方針にした．
疑似コードっぽいものを書いているうちに，最後に弧が交わるケースだと弧の軌跡の長さを覚えているだけでは対処できないことに気付く．
でもそれなら弧をそれぞれ全部記憶しておいて，後で比較しつつ交わるなら交点を求める，という風にすればいいのでは，と思った．
これで大まかな方針は固まったものの，場合分けがしんどい．それと弧と弧の交差判定と交点をどうやって求めよう？という問題もあった．
なんか E を通せたらしい．すごい．
F の方針を説明して，いくつかツッコミを受けてから書き始める．
が，バグバグで全然求めていた値が出ない．何度も指摘されて修正していくものの結局そのまま終了．
E を解いてくれた2人に感謝．
噂によると GCJ だと Presentation Error は Wrong Answer ではなく単に弾かれるだけらしいので，アウトプットに Case #n を強制するなどして ICPC もそういうシステムになるといいのでは…
幾何修行の必要性は自分でも感じたし，kinosaki さんにチームで1人は幾何問題に対して実装しきるよう修行しないとと言われたので，幾何から逃げずに修行しようと思います．
*1:本当にインプットを送っていたかどうかは謎
