確率を確実に

問題概要

正の整数 $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;
}

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

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

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

問題概要

制約

考えたこと