期待値に関するセンスがちょっと求められる問題

問題概要

高橋君はテストケースが $N$ ケースある Yes/No 判定問題に対して、ソースコードを提出したところ $M$ 問で TLE して、残りの $N-M$ 問は正解しました。

そこで「 $N-M$ 問については 100ms で正解し、残りの $M$ 問に対しては 1900ms で打ち切って Yes/No をランダムに出力するプログラム」を AC がもらえるまで提出し続けることにしました。

AC するまでにかかる時間の期待値を求めよ。

制約

$1 \le M \le N \le 100$
$1 \le M \le 5$

考えたこと

プログラムは毎回、 $1900M + 100(N-M)$ ms かかることから、AC がもらえるまでの回数の期待値を $e$ とすれば、求める期待値は

$(1900M + 100(N-M))e$

となることがわかる。よって問題は、AC がもらえるまでに提出する回数の期待値を求める問題へと帰着された。

一般論

以下のことがらは大変有名であり (覚えてしまってもいいくらいだと思う)、直感的にも納得がいく！！！

確率 $p$ で成功するミッションを成功するまでトライし続けたとき、トライすることになる回数の期待値は $\frac{1}{p}$ である

これは直感的には「それはそう」という感じである。つまり、例えば確率 $1/2$ で成功するミッションは平均 $2$ 回で成功する気持ちになれるし、確率 $1/100$ で成功するミッションは平均 $100$ 回で成功する気持ちになれる。もう少し複雑な例として確率 $\frac{99}{100}$ で成功するミッションは平均 $\frac{100}{99}$ 回で成功する (多くの場合 1 回で成功するので 1 をちょっと超えた値になる)。

これを使えば、この問題は簡単で、

$M$ ケース全部通る確率は $(\frac{1}{2})^{M}$

となることから、

AC するまでに試行する回数の期待値は $2^{M}$

となる。

#include <iostream>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    long long teisyutu_kaisuu = 1LL<<M;
    long long each_time = 1900LL * M + 100LL * (N - M);
    cout <<  each_time * teisyutu_kaisuu << endl;
}

証明

一応一般論を 2 通りの方法で証明してみる。

証明 1: 期待値漸化式

この考え方は、期待値 DP を組む時などにもすごく有効なので是非に！！！

求める期待値を $E$ とおいて、 $E$ を式で表すために場合分けをする。

次の試行で失敗するとき、その確率は $1 - p$ である。そして、そこから終わるまでの回数の期待値も $E$ なので、最初からの試行回数の期待値は $E + 1$ になる。まとめると $(E + 1)(1 - p)$
次の試行で成功するとき、その確率は $p$ である。そしてその時点で終了するので、最初からの試行回数の期待値は $1$ になる。まとめると $p$