きままにものづくり

日々の気付いたことなんかを書いてます。

dwango2015C

問題


C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

解法

n回ラウンドを行い、引き分けが続くときの期待値は以下となる。
1*(1-d)*d^{0} + 2*(1-d)*d^{1} + ... + n*(1-d)*d^{n-1}
ここで、dは引き分けとなる確率を示し、(1-d)は勝者が決まる確率を示す。
あいこ以外の結果が出る時のラウンド数の期待値は上の式となる。求めたいのは最後の一人になるときのラウンド数の期待値なので、あいこ以外の結果が出て人数が減った時の期待値wも求める必要がある。
wは動的計画法により求めることができる。wを考慮した場合の式は以下となる。
\{1*(1-d)*d^{0} + w*d^{0}\} + ... + \{n*(1-d)*d^{n-1} + w*d^{n-1}\}
誤差の範囲が指定されているので、nを100ぐらいにすれば誤差の範囲内で答えを出すことが可能である。
上の式は無限級数の和として求めることができる。
(1-d)\sum^n_{i=1}(i*d^{i-1}) + w\sum^n_{i=1}d^{i-1}
無限級数の和の公式である
1+e+e^2+...+e^n \xrightarrow{n\rightarrow\infty}\frac{1}{1-e} (-1 < e < 1)
を用いると
\frac{1}{1-d} + \frac{w}{1-d}
となる。

計算量

O(N^3)
N:ゲームの参加人数

コード