Google Code Jam 2013 Round 1A

Round 1Aがありました。
上位陣のソースを見て復習しました。

Problem A. Bullseye

二分探索の問題。 i番目（i=1,2,...）の黒い円の面積は、Si = (2 * r + (4 * i - 3))πと表すことが出きるので、円をN個塗った場合の面積の合計値は、ΣSi = (2 * N² + (2 * r - 1) * N)πとなる。 Nが決まれば面積が決まり、塗料が足りているのかどうかはO(1)で判定できる。よってNを二分探索で決めればいい。

Problem B. Manage your Energy

動的計画法で解く。今i番目までのタスクが最適にこなされているとする。
そこに(i+1)番目のタスクを加えたときに、i番目までの解を後ろから走査していきより（i+1）番目のタスクに多くのエネルギーを使った方がいいのかどうかを見ていけばいい。

Problem C. Good Luck

確率の問題。観測される積の列がprとなる確率をp(pr)とおく。選ばれたカードの集合がxとなる確率をp(x)とおく。事後確率p(x | pr) = p(pr ∧ x) / p (pr)が最大となるようなxを出力すればいい。p(pr)はxによらず一意なので、p(pr ∧ x)が最大となるようなxを計算する。計算量を減らすためにxのpermutationは考えずに、xが非減少列となるようなものだけを考えて、確率を計算するときにpermutationを数えてあげるといい。