hotpepsiの練習帳

SRM 615

シミュレーション | 02:33

Div1 Easy (250) AmebaDiv1

問題

• アメーバのモンテカルロは、自分と全く同じ重さのゼリーだけを食べる
• ゼリーを食べると体重が2倍になる
• ゼリーの重さが出現順に与えられる
• モンテカルロが到達しない重さの組み合わせの総数を求める

方針

• ゼリーに含まれない大きさだったときは何も食べないので無関係
• ということはゼリーに含まれる大きさだけを考えればいい
• 元々の大きさがaだったとき、最終的にa*2^nになるので、aが到達しない候補となる
• a*1/2のゼリーが含まれているとaになることがあり、それを候補から除外する
• まずゼリーに含まれる大きさにそれぞれについてシミュレーションしておく
• ゼリーに含まれる大きさのうち、到達しないものを数える
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_615/AmebaDiv1.cpp

結果

o-- 211.75pt 323/727th rating 1439 -> 1477 (+38)

落ち着いて解けた。なかなか良い点数。

乱数は出てこなかった。

http://togetter.com/li/650989