Search on the blog

2013年4月27日土曜日

Google Code Jam 2013 Round 1A

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

Problem A. Bullseye
二分探索の問題。 i番目(i=1,2,...)の黒い円の面積は、Si = (2 * r + (4 * i - 3))πと表すことが出きるので、円をN個塗った場合の面積の合計値は、ΣSi = (2 * N2 + (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を数えてあげるといい。

0 件のコメント:

コメントを投稿