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

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

AtCoder ABC 126 C - Dice and Coin (300 点)

確率を確実に

問題へのリンク

問題概要

正の整数  N, K が与えられる。
最初に  1 〜 N の整数値をランダムに出力する。以降コインを振って

  • 表が出たら整数値を 2 倍する ( K 以上になったら「勝ち」でゲーム終了)
  • 裏が出たら整数値を 0 にする (こうなった時点で「負け」でゲーム終了)

というのを繰り返す。勝ってゲームを終了する確率を求めよ。

制約

  •  1 \le N, K \le 10^{5}

考えたこと

制約が小さいので、最初に出てくる数値をすべて試すことができる。具体的には

  • 最初に  v (= 1, 2, \dots, N) が出る確率は  \frac{1}{N} になる
  • さらにそこから勝つ確率は、 v からスタートして  K 以上になるまで表が出続ければよくて、表が出る必要のある回数を  n とすると、  (\frac{1}{2})^{n} になる

ということで、合計して、

  •  \frac{1}{N} × (\frac{1}{2})^{n}

となる。これを  v = 1, 2, \dots, N について合計すれば OK。

最後に気になるのは  n (各  v からスタートして  K 以上になるまでに出し続ける必要のある表の回数) の求め方だが、これは愚直に

int n = 0;
while (v < K) v *= 2, ++n;

とかで大丈夫。このとき  v は指数的に大きくなるので、計算回数は  O(\log{K}) で抑えられる。以下の実装ではさらに、

  •  (\frac{1}{2})^{n}

の計算も while 文の中でまとめて行うこととした。全体として計算量は  O(N\log{K}) になった。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;
    
    double res = 0.0;
    for (long long n = 1; n <= N; ++n) {
        double tmp = 1.0;
        long long nn = n;
        while (nn < K) nn *= 2, tmp /= 2.0;
        res += tmp;
    }
    res /= N;
    cout << fixed << setprecision(10) << res << endl;
}