Project Euler - Problem 286

Scoring probabilities

Barbara は数学者でありバスケットボール選手である. 彼女は, 距離 x からシュートしたときに得点できる確率がちょうど (1-x/q) であることに気づいた. ここで q は 50 よりも大きな実定数である.

各予行練習では, 彼女は距離 x=1, x=2, ..., x=50 からシュートする. 記録によると, 合計点が 20 点ぴったりになる確率はちょうど 2 ％である.

q を求め, 小数第11位を四捨五入して答えよ.

(日本語訳より)

確率 DP と二分探索．

距離 x でのシュート成功確率を

p(x) = (1 - x/q)

とする．

dp[n][k] = (n 本目まで投げて k 本成功する確率)

とおけば，

dp[0][0] = 1
dp[n + 1][k] += (1 - p(n + 1)) * dp[n][k]
dp[n + 1][k + 1] += p(n + 1) * dp[n][k]

という更新式が生える．

ループを回した後の dp[50][20] が 50 本投げて 20 本成功する確率なので，これが 0.02 に近付くような二分探索を書けばいい．

#include "bits/stdc++.h"
using namespace std;
template<typename A, size_t N, typename T> void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }


double p[64];
double dp[64][64];

int main()
{
    clock_t start, end;
    start = clock();

    double l = 50, q, r = 60;
    while (r - l > 1e-13) {
        Fill(dp, 0.);
        q = (l + r) / 2;
        for (int x = 1; x <= 50; x++) p[x] = 1 - x / q;
        dp[0][0] = 1;
        for (int n = 0; n < 50; n++) {
            for (int k = 0; k < 50; k++) {
                dp[n + 1][k] += (1 - p[n + 1]) * dp[n][k];
                dp[n + 1][k + 1] += p[n + 1] * dp[n][k];
            }
        }
        if (dp[50][20] < 0.02) r = q;
        else l = q;
    }

    printf("%.10f\n", q);

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

2 msec くらい．

こういう問題が解けるようになってきたのは素直にうれしい．

絶滅

どうでもいい

Project Euler - Problem 286

Scoring probabilities