[競プロ] ABC/ARC085 C問題を無限級数の知識なしで解く

他意はありませんが、AtCoder Beginner Contest / AtCoder Regular Contest 085 のC問題を、無限級数の知識なしで、for文を使ってコードをいっぱい書いて解いてみます。

1回の試行で失敗する確率は 1/2 なので、n回失敗し続ける確率は急速に（指数関数的に）減少することが予想できます。

従って、forループで近似すれば短い時間で解けることが予想できます。

まず、最初の1回で成功する確率は、次のようになります。

\[ \left(\frac{1}{2}\right)^M \]

また、2回目で成功する確率は、次のようになります。

\[ \left\{ 1 – \left(\frac{1}{2}\right)^M \right\} \left(\frac{1}{2}\right)^M \]

このように計算すると、1回の試行に掛かる時間をTとして、求める期待値は、次のように表せます。

\[ E = \left(\frac{1}{2}\right)^M T + \left\{ 1 – \left(\frac{1}{2}\right)^M \right\} \left(\frac{1}{2}\right)^M \times 2T + \left\{ 1 – \left(\frac{1}{2}\right)^M \right\}^2 \left(\frac{1}{2}\right)^M \times 3T + \left\{ 1 – \left(\frac{1}{2}\right)^M \right\}^3 \left(\frac{1}{2}\right)^M \times 4T + \cdots \]

ただし T は、

\[ T = 1900M + 100(N-M) \]

となります。これは、i回目まで失敗し続ける確率 $$ P_i $$ と、期待値の第i項までの総和 $$ E_i $$ を用いて、次のように漸化式で表すことが出来ます。

\[ \begin{split} P_0 &= 1 \\ P_{i+1} &= \left\{1 – \left(\frac{1}{2}\right)^M \right\} P_i \\ E_0 &= 0 \\ E_{i+1} &= E_i + \left(\frac{1}{2}\right)^M P_i \times (i + 1)T \end{split} \]

このとき、E は極限で求められます。

\[ E = E_\infty \]

これをプログラムに書き起こすと期待値が計算できます。

var N = 100;
var M = 5;

var p_current = 1.0;  // i 回目まで失敗し続ける確率
var E = 0.0;          // 求める期待値
var time_elapsed = 0; // (i + 1) 回目までの経過時間

for(var i = 0; i < 10000; i++) {
  // (i + 1) 回目で成功する確率と失敗する確率を計算
  var p_succ = Math.pow(0.5, M);
  var p_fail = (1 - Math.pow(0.5, M));

  // 成功した場合に掛かる所要時間を計算
  var time_succ = 1900 * M + 100 * (N - M);

  // 期待値を計算するための項を加算
  E += (p_current * p_succ) * (time_elapsed + time_succ);

  p_current *= p_fail;
  time_elapsed += time_succ;
}

alert(Math.round(E));  // 608000