GoogleCodeJam R2

ギリギリで通るなどしたのでR2参加できました。
結果はRank: 756 Score: 31。B完+C-smallです。残念ながらTシャツは獲得ならず。
以下記録。
とりあえず問題を読み始めて、Aの得点が低いから簡単なんだろうと思って15分ほど考えるも無理と悟って放棄。そのあとB,C,Dと読んでいたら、Cのポスト数が増えてきたのでとりあえずCを解いてみる。
Largeの解法は思いつかなかったので、とりあえず取れるとこだけ取っておこうと言うことで、愚直に盤面をシミュレートするプログラムを書いて投げてAC。6pt。
この時点で40分くらい経過していたので、ここで得点低いAを解いてもしょうがないと思ってBとDに標的を絞る。で、Dは複数の円の共通部分の面積を求める問題で、よくわからないので放置。Bは英語がよくわからなかったのでYahoo翻訳の助けを借りながら読んで、なんかDPぽいしDよりは楽じゃないかと思って解き始める。
・・・が、どう分割すればいいかよく見えない・・・。どうしよー、と思い始めたところで、チーム数が高々2**10であることに気づく。2分木の深さは高々10なんだから、これはちゃんと枝刈りすれば全探索いけんじゃね・・・！ということで、Rootから順にチケットを買う・買わないを全探索していき、条件を満たせなくなったところで探索を打ち切るような再帰関数を書く。
思いのほか手間取って、終了5分前に完成。速攻でsmallをポスト！通った！よしlargeだ！残り1分で提出完了し、合計31pt。

一番の反省点は、Bの実装に手間取って1時間くらい費やしてしまったこと。Mのインデックスがチーム番号だし、チケットの木は完全2分木だから、構造体を作るより一次元配列で取ったほうがいいと判断したまではよかったんだけど、肝心の完全2分木の処理で悩んで時間を食うという・・・。この辺はちゃんと復習しとこう。
あと、終わってから教えてもらって気づいたけどD-smallは牛2匹なのね・・・。これならすぐに計算できたはずだから勿体無い。まあ、Bの終了時刻を考えると、これ解いてたらBは解けてない可能性が高いからどっちにしろダメなんだけど。
来年こそはTシャツ欲しい！それともっと余裕でR1を終わりたい！