ABC 078 C - HSI - BEN2のブログ

ABC 078 C - HSI に関連する、期待値についてのメモを残します。

参考

何回引いたら当たる？

当たりが何本か入ったくじがある。くじを 1 本引くとき、当たりを引く確率を $p \, (0 \lt p \leq 1)$ とする。引いたくじはすぐに戻す。当たりを引くまで繰り返しくじを引くとき、くじを引く回数の期待値は $\displaystyle \frac{1}{p}$ である。

証明

$q = 1 - p$ とする。
1 回目で当たりを引く確率は $p$ 、2 回目ではじめて当たりを引く確率は $qp$ 、 $n$ 回目ではじめて当たりを引く確率は $q^{n-1} p$ であるから、求める期待値を $E$ とすると

$\begin{aligned} E &= p + 2 q p + \cdots + n q^{n-1} p + \cdots \\ &= p \sum_{n=1}^{\infty} n q^{n-1} \end{aligned}$

である。ここで

$\begin{aligned} \sum_{n=1}^{\infty} n q^{n-1} &= 1 + 2q + \cdots + nq^{n-1} + \cdots \\ &= {(q)}^{\prime} + {(q^{2})}^{\prime} + \cdots + {(q^{n})}^{\prime} + \cdots \\ &= \frac{d}{dq} \sum_{n=1}^{\infty} q^{n} \end{aligned}$

であり、 $0 \leq q \lt 1$ であるから

$\displaystyle E = p \, \frac{d}{dq} \sum_{n=1}^{\infty} q^{n} = p \, \frac{d}{dq} \frac{q}{1-q} = p \, \frac{1}{{(1-q)}^{2}} = \frac{1}{p}$

何回提出したら AC ？

問題 : ABC 078 C - HSI

1 回の操作 (実行) にかかる時間は $1900M + 100(N - M)$ ms
1 回の操作で $M$ ケース全て正解する確率は $\displaystyle \frac{1}{2^{M}}$ なので、操作回数の期待値は $2^{M}$

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M; cin >> N >> M;
  cout << (1900*M + 100*(N-M)) * pow(2, M) << endl;
}