Google Code Jam 2009 Round2備忘録

まだ全部解けてないけど、忘れないうちに書いておく。
結論から言うと去年よりひどい負け方でおわた。

まずA問題を見る。最初隣のセルを交換するのかとおもって実装めんどくせーと思って飛ばした。miss++
次にB問題を見る。smallでも60セルとかメモ化しても2^60かよとか思って飛ばす。
次にD問題を見る。最初、2つのスプリンクラーでplantを部分的に覆う場合とかあるんじゃないのかなとか考えてしまったのがmiss++
その間に30分ほど経過してしまって、A問題がボコボコ解かれていくのでA問題に戻る。テストの3問目が通らないことで行を交換することに気づく。だがそれでも最短のアルゴリズムは見いだせず、結局手間はかかってもいいからDPで解くことに。smallが通ったのは50分ぐらい経ってからだった・・
次にD問題で部分的に覆うことはないことに気づきそそくさと書いてCorrect. D-largeもすこし考えるが、三角形の各頂点からの長さが共通の一変数の式で表される点の座標と半径を求めなければいけないことがわかって意気消沈。やめとく。まともに解くと3元2次連立方程式が出てきてうう゛ぇーと・・
この時点で66分だったので、Cが解けてさらにもう一題解けなきゃ厳しいだろうなとおもってCへ。
完全部分グラフの最小構成だなーとか問題をさらに複雑にするようなことを考えて、smallでは解けそうだったので書いてsubmit・・だが通らない！
そのまま泣きわめきながら終了。

まず、A問題だが、どうやらバブルソート崩れでいいらしい。だが数学者?の性か最小性が言えなければ手を出さないのが仇になってしまった。要検証。
B問題は結局手を付けなかったが、1行中で掘る部分が必ず連続してなければいけないということに気づけば、smallもlargeも解ける。終了後に解いたら76分で全部できた。
C問題は偉い方の記事を見るに、2部グラフのマッチングらしい。どこかできいたようなことだけど、これは頭にたたき込んでおきたい。
D問題は、方針は合っていたが、終了後のコーディングも相当時間がかかってしまった。やはり連立方程式をそのまま解くのはどうにも汚くめんどくさくなりそうなので、ヘロンの公式＋二分検索で半径を求めてから、2元1次の連立方程式を解く形にもっていった(手元の実行時間だと44秒程度)が、求めた値を再代入すると誤差がすさまじく出て、こんなんでいいのかと思ってしまう。

ちなみにC問題が通らなかった理由は、グラフの大小をみるのにintの乗算をしてて、これがオーバーフローしてた、ただそれだけでした。爆発しろ！