JAG春コンテスト2014
binding.pryで参加した。 7問解いて7位。WF進出チームの中では4チーム中3位。ぐぬぬ……。 コード一覧。
以下ログ。 時刻はだいたい。
13:00
ギリギリセーフで集合時間に間に合う。 とこはるさんが研究室のプリンタで問題を印刷している間にBを読んで、とこはるさんに投げることを決める。
CとDも読む。 Cはよくわからん、Dは構文解析っぽいけど?多いしやばそうだなぁと思う。
13:20
このへんで印刷が一段落してとこはるさんが合流する。 mikecatさんが読んでたAが簡単そうだととこはるさんが主張したので、mikecatさんと考えてもらう。 その間にGとIを読む。
13:30
AはLCAするだけらしい。 自分はダブリング配列作るところで何回もバグった記憶があって嫌だなぁと思い、とこはるさんに書いてもらう。
13:40
とこはるさんがダブリング配列書いたところで詰まっていたので、細部を確認しつつ引き継ぐ。
13:50
書き終わる。バグる。 他の問題を考えようかと思ったけど、みんな通してるっぽいのでペアプロでがんばる。
14:13
添字ミスと二分探索の解釈ミスだった。 サンプル通ったので投げる。ようやく1AC(+73min)。 この時点で26位とかで絶望感ある。
mikecatさんがHを理解したらしいので任せる。 とこはるさんにはBを考えてもらう。
その間に解けそうなやつを考える。 Eは端で残ってるカッコの開閉だけ考えればよいのでDPとかでいけそう。
14:20
開けるだけ開いといて損はないので、DPせずともGreedyでいける気がしてきた。 Nimと聞いていたのでJを読んでみる。
14:30
Grundy数が自分と相手で解釈が違ってやばそう。 mod gcd(A,B)+1 とかで考えるとうまくいくんでは？みたいなことを考える（大嘘）。
14:48
mikecatさんがHを書き終える。AC(+35min)。 とりあえずやるだけっぽいEを書く。
14:56
サンプルが通ったので投げる。WA(+8min)。 とこはるさんがBのコードを完成させていたので交代する。
mikecatさんとEのデバッグ。 Greedyでよさそうだけどなんで落ちるのか分からない。 PCが開いたらYesになるようなランダムケースを生成してNoが出るか確かめようということになる。
15:10
Fを眺めていて、これ可視グラフ作って適当に頂点カバーするだけではと気付く。 頂点カバーだけなら解けるけど、幾何パートがちょっとつらそうということを伝えて放置。
15:25
とこはるさんがBを書き終える。投げる。AC(+29min)。
mikecatさんとEのデバッグ。 Rubyで50文字くらいのバランスしたカッコ列を適当に生成して分割するコードを書く。 何回か食わせたらNoが出たので、すかさずmikecatさんが書き写して調査する。
15:40
最後に閉じるところで、開いてるカッコがちょうど0になるようなやつを残しておかないと詰むことを指摘される。 確かにそうだ。 直して投げる。AC(+15min)。
このへんで順位表を見たら1ページ目に来ていて安心する。
確実に解けているやつがなくなったので、とりあえずとこはるさんにJ、Cを任せつつ、自分はFの頂点カバー部だけ書く。 mikecatさんには幾何パートを考えてもらう。
15:55
とこはるさんがDを見て、区間DPで解けると主張する。 言われれば確かにそうだ。
16:25
適当に実装したらサンプルが合ったので投げる。AC(+45min, Dのみでは+30min)。
Cは51次の多項式重みでフローを流せばよいととこはるさんが主張する。 多倍長を用意するのが面倒だったので、52次元ベクトルを適当に演算子オーバーロードして実装することにする。 haskell-lover由来のフローライブラリは変数の型がテンプレート化されていて、こういうとき楽でよい。
16:55
実装したけど間違えて最大流を貼ってた（ひどい）。最小費用流に直す。 Primal DualってDijkstra使ってるけど負コストつっこんでも大丈夫なんだっけ、とりあえず試してダメそうだったら考えようとか話しつつ実装する。
17:12
サンプルが合ったので投げる。AC(+47min)。
残り時間が少ない。 とこはるさんがJはmod min(A,B)+1でどうでしょうと言っていたので試すも、サンプルすら合わなかった。
mikecatさんが、多角形の各点をすこし外側に摂動することで安全に可視判定ができると主張していたので、とりあえず実装してもらう。 その間にIをとこはるさんに説明する。
17:40
mikecatさんが幾何パートを実装し終えたのでサンプルを食わせてみる。なんかおかしい。 可視グラフがそもそも間違っているっぽい。
17:50
内積と外積の式を間違えていたらしい。 直したら今度は頂点カバーが終わらないので、枝刈りとか入れてみるけど変わらず。
17:57
printfデバッグしたら無限ループにハマっていた。 直して投げる。AC(+45min, 前に書いたところと合わせて+60min)。 後で考えたら枝刈りを1箇所間違えている気がするけど、なんか通ってしまった。
四川
とこはるさんがJを場合分けで解く方法を思いついて実装する。 3ケースだけWAが出たとのこと。
反省
毎度のことながら初動が遅い。 6位のYellowYellは9WAしているのに、それでもペナルティの差で負けているあたり、速度面ではもっと改善点がありそう。
バグらせまくってハマるということはあまりなかった（Aはハマったけど）ので良かった。
自分ではAのLCAの実装をぱっと書けなかったこととか、 Cがフローであることが見えなかった（というかこの形知らなかった）とか、 可視グラフはWelcome to Hellで有名な例のアレで書いたはずなのに自信がないとか、 知識面の薄さが遅れに繋がっているように思った。