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; }
感想
普通に難しいと思うんだけどナア.
めっちゃ簡単じゃんと言われたことがあり,とてもつらい気持ちになっています.