けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 085 C - HSI (300 点)

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

問題へのリンク

問題概要

高橋君はテストケースが  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

以上を合わせて、

 E = (E + 1)(1 - p) + p

という方程式が立てられる。これを  E について解くと、

 E = \frac{1}{p}

が得られる。

証明 2: 無限級数

素直に期待値の定義に沿って計算する。期待値の定義とは、 k 回で終わる確率を  P_k として

 E = \sum_{k = 1}^{\infty} kP_k

である。一見非自明なのだが、これは実は

  •  Q_k := 成功までに  k 回以上かかる確率

として

 E = \sum_{k = 1}^{\infty} Q_k

となる。イメージとしては下図のような感じ。左側が  \sum_{k = 1}^{\infty} kP_k という式を表していて、右側が  \sum_{k = 1}^{\infty} Q_k という式を表している。

f:id:drken1215:20190323174851p:plain

よって  Q_k を求めればよく、これは「 k-1 回目までに成功しない確率」なので

  •  Q_k = (1 - p)^{k-1}

となる。よって求める期待値は

 E = \sum_{k = 1}^{\infty} Q_k
 = \sum_{k = 1}^{\infty} (1 - p)^{k-1}
 = \frac{1}{1 - (1 - p)}
 = \frac{1}{p}

と求められる。