ABC078 C問題 : HSI - 忘れても大丈夫

問題. HSI

$N$ 個のテストケースを解くプログラムを書いた．どの提出でも， $M$ ケースはそれぞれ確率 $1 / 2$ で正解して各実行時間が 1900 ms となる．残りの $N - M$ ケースではそれぞれ必ず正解して各実行時間が 100 ms となる．すべてのテストケースが同時に正解するまで提出することを繰り返したときの総実行時間の期待値を求めよ．

制約： $1 \le N \le 100$ ，　 $1 \le M \le \min\{N, 5\}$

解法. 不公平な硬貨投げ

1回の提出を行ったときの実行時間の総和を $t$ とすると， $t = 1900 M + 100 (N - M)$ となる．また， $M$ 個のすべてのテストケースが正解する確率は $p = (\frac{1}{2})^M$ である．このとき，少なくとも1つのテストケースで不正解となる確率は $q = 1 - p$ である．
1回の提出を，表が出る確率が $p$ の不公平な硬貨を1回投げる試行と同一視すると，この問題の答えは，初めて表が出るまでに硬貨を投げた試行回数の期待値の $t$ 倍に等しい．したがって，初めて表がでるまでに投げた試行回数の期待値を求めることを考える．
表が出るまで投げた回数を $i$ としたとき，この確率は $q^{i - 1} p$ となるので期待値は，
　 $\sum_{i = 1}^{\infty} i q^{i - 1} p = p \sum_{i = 1}^{\infty} i q^{i - 1} = p \frac{d}{dq} (\sum_{i = 1}^{\infty} q^i) = p \frac{d}{dq} (\frac{q}{1 - q}) = p \frac{1}{(1 - q)^2} = \frac{1}{p}$
となる．したがって，答えは $\frac{t}{p}$ である．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll n, m;
    cin >> n >> m;

    ll t = 1900 * m + 100 * (n - m);
    ll inv_p = 1 << m;
    cout << t * inv_p << endl;

    return 0;
}

まとめ

ABCのC問題ということは典型らしいので，表が出るまでの回数の期待値は確率の逆数という事実を覚えとく（いちいち導出していたら時間がかかる）．
ちなみに，期待値の計算を愚直に行うと数値誤差で不正解となるので注意．