ARC055 B - せんべい

解法

dp[i][j][ate_max] := i 番目まで見て,j 個食べていて,現時点で最大のものを食べている(ate_max: bool) 状態から始めたとき,最終的に N を食べられる確率
と定義する.
dp[N][j][1] が,確率 1 に相当する.(N 枚まで見て max を食べているなら,それは N にほかならない.この状態から始めれば当然確率 1.)

遷移は,以下の3通り.
1. 今食べようとしているせんべいが過去最大であり,それを食べる
2. 今食べようとしているせんべいが過去最大であり,それを食べない
3. 今食べようとしているせんべいは過去最大でないため,それを食べない

過去最大でないせんべいを食べる必要性は全く無いので,それは考えない.
今食べようとしているせんべいが過去最大である確率は,nCi * (i - 1)! / (nPi) = 1/i となる.ケース1 と 2 の大きい方と,3 を足し合わせたものが答え.

ソースコード

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

int N, K;

double rec(int n, int k, bool ate_max, vector<vector<vector<double>>>& dp) {
    double& res = dp[n][k][ate_max];
    if(res != -1) {
        return res;
    }
    if(n == N) {
        return res = ate_max;
    }

    res = 0;

    // 今見ているせんべいが今までで最大である場合 食べる or 食べない
    double eat = (k < K ? 1.0 / (n + 1) * rec(n + 1, k + 1, true, dp) : 0);
    double not_eat = 1.0 / (n + 1) * rec(n + 1, k, false, dp);
    res += max(eat, not_eat);
    // 今見ているせんべいが今までで最大でない場合 食べないのが最善
    res += 1.0 * n / (n + 1) * rec(n + 1, k, ate_max, dp);
    return res;
}

int main() {
    cin >> N >> K;
    vector<vector<vector<double>>> dp(N + 1, vector<vector<double>>(K + 1, vector<double>(2, -1)));
    cout << fixed << setprecision(10) << rec(0, 0, 0, dp) << endl;
}

感想

普通に難しいと思うんだけどナア.
めっちゃ簡単じゃんと言われたことがあり,とてもつらい気持ちになっています.