なぜか埋め込みにこだわってしまい、本番 AC できなかった...

問題へのリンク

問題概要

整数 $P, W$ が与えられる。以下の条件を満たす最大の正の整数 $N$ を求めよ (存在しない場合は -1、無限個存在する場合は -2)。

確率 $P$ % で表が出るサイコロを $N$ 回振るとする
表が出た回数を $a$ をしたとき、 $W \times a - N$ のスコアを獲得するものとする
このとき、獲得スコアが正である確率が $\frac{1}{2}$ より真に大きい

制約

$0 \le P \le 100$
$0 \le W \le 100$

考えたこと

順位表を見て、誤差がキツかったりするのかなとか思った。丁寧に場合分けして考えることにする。まず

$W \le 1$ のときは -1
$P = 50, W = 2$ のときは -1 (ちょうど $\frac{1}{2}$ にはなるが超えることはない)

というところまではすぐにわかる。さらに

$P \times W \gt 100$ であれば -2

ということもわかる。これは中心極限定理から示せる。 $N$ 回の試行で得られるスコアの分布が $N \rightarrow \infty$ では正規分布に近づいていくが、その平均値が 0 より真に大きいからだ。さらに上手く証明できなかったが $P = 50, W = 2$ 以外の $PW = 100$ の場合も -2 になるっぽかった。

さて、それ以外の場合については、

$n \equiv W - 1 \pmod W$

という場合のみ考えればよく、その場合については $n$ について単調減少となっている。はじめて $\frac{1}{2}$ 以下になる瞬間をとらえれば OK。

ここでは誤差を恐れて、二項係数計算をするのではなく DP でやった。long double 型で十分通った。

コード

#include <bits/stdc++.h>
using namespace std;

long double solve(int P, int W) {
    if (W <= 1) return -1;
    if (P == 50 && W == 2) return -1;
    if (P * W >= 100) return -2;
    
    long long res = -1;
    vector<double> dp({1.0});
    for (int n = 1; n < 10000; ++n) {
        vector<double> ndp(dp.size() + 1);
        for (int i = 0; i < dp.size(); ++i) {
            ndp[i+1] += dp[i] * P / 100;
            ndp[i] += dp[i] * (100 - P) / 100;
        }
        swap(dp, ndp);

        if (n % W == W - 1) {
            long double prob = 0.0;
            for (int i = 0; i < dp.size(); ++i) {
                if (W * i - n > 0) prob += dp[i];
            }
            if (prob > 0.5) res = n;
            if (prob < 0.5) break;
        }
    }
    return res;
}

int main() {
    int P, W;
    cin >> P >> W;
    cout << solve(P, W) << endl;
}

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

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

Xmas Contest 2020 B - Beterminant

問題概要

制約

考えたこと

コード