水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

技術室奥プログラミングコンテスト #3:E - デフレゲーム

問題

beta.atcoder.jp

解法

何回目に操作が終了するかで場合分けをする.k 回目に操作が終了する確率は

(n / n) * ( ( n - 1 ) / n) * ( ( n - 2 ) / n) * ... * ( ( n - ( k - 2 ) ) / n) * ( ( k - 1 ) / n)

になる.k 回目までのさいころの目の数の和の期待値は,1回あたりの期待値が (n + 1) / 2 であるので,

k * (n + 1) / 2

になる.あとは 2 <= k <= n + 1 のそれぞれの k に対して確率と目の数の和の期待値を掛け合わせた和を求めればよい.確率を求める際,k ごとに一回一回求めていては計算量が O(n^2) となってしまうので,k - 1 回目の時の確率を利用する形で k 回目の時の確率を求めると O(n) にすることができる.

解答

beta.atcoder.jp

さいころの目の数の和の期待値を利用せずに解こうとしていて 1 WA.確率については自分で一から求めることが出来た.

f:id:babcs2035:20181031223811p:plain