hotpepsiの練習帳

Google Code Jam 2013 Round 1B

18:17

A. Osmos

問題

• 物体を吸収していくゲーム
• N個の物体と、手持ちの物体の重さが与えられる
• 手持ちの物体より軽い物体は吸収でき、その重さが加わる
• 場に任意の重さの物体を追加するか、または、場の任意の物体を除外することができる
• 全ての物体を吸収するために必要な、追加または除外の操作回数を求める

方針 (small, large)

• 貪欲
• N個全てを除外するのが最大値
• 1個ずつ吸収していく
• 自重より軽いものがない場合は、自重の-1の重さのものを追加して、追加回数をカウントしておく
• 残りを全て除外したと仮定して、最小値を更新する
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_A.cpp

B. Falling Diamonds

問題

• ダイアモンドが上から落ちてくる
• 下にダイアモンドが存在する場合、左か右に積もっていく
• おおむね三角形になる
• 落ちてくる総数と、座標(X,Y)が与えられる
• その座標にダイアモンドが積もる確率を求める

方針 (small)

• (終了後)
• 1個,5個,9個...と、4x+1個ずつ、三角形に積もる
• 頂点を除き、片側に積もる最大の個数は|X|+|Y|
• 三角形の内側なら1.0、完全に外側なら0.0、その間なら計算する
• 両側にlength個ずつ落ちる場所があり、N個落ちてくるときの確率を求める
• 左に落ちる場合を0、右に落ちる場合を1として、Nビットを全列挙して足す
• ただし、片側にlength個以上落ちた場合は、反対側に落ちたものとして計算する
• 落ちる個数はpopcount(x)＋max(0,popcount(~x)－length)
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_B_s.cpp

方針 (large)

• (終了後)
• kmjpさんのブログを読む
• DPで計算できるっぽい
• i個落ちてきたときの確率テーブルがあり、i+1個目が落ちてきたとする
• j個存在するが確率Pとする
• 1/2でこちらに落ちない(反対側に落ちる)ので、dp[i+1][j]に0.5×Pを加える
• 1/2で落ちるので、dp[i+1][j+1]に0.5×Pを加える
• すでにlength個落ちている場合は、反対側に落ちるので、dp[i+1][length]にはdp[i][length]を加える
• 反対側にlength個落ちている場合は、こちらに落ちるので、dp[i+1][length+1]にdp[i][length]を加える
• length=6のときのテーブルは以下の通り

i	0個	1個	2個	3個	4個	5個	6個	7個
0	0.500	0.500
1	0.250	0.500	0.250
2	0.125	0.375	0.375	0.125
3	0.063	0.250	0.375	0.250	0.063
4	0.031	0.156	0.313	0.313	0.156	0.031
5	0.016	0.094	0.234	0.313	0.234	0.094	0.016
6	0.000	0.063	0.164	0.273	0.273	0.164	0.063	0.000
7	0.000	0.000	0.145	0.219	0.273	0.219	0.145	0.000	0.000
8	0.000	0.000	0.000	0.254	0.246	0.246	0.254	0.000	0.000	0.000

• 次の行に0.5倍ずつしたものを加える形になっている
• 行の合計値が1.0
• 7個以上落ちてきたとき、6個までしかたまらない
• 7個落ちてきたとき、1個しかない場合は存在しない
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1B_B_l.cpp

結果

A small+large 22pt 1584th/4678

Bはビット列挙を思いつかず。面白い問題だった。