AtCoder Regular Contest 055 B: せんべい
解法
dp[n][k] := n 枚のうち k 枚食べることができる場合のNのせんべいを得られる確率、とおく。
食べるかどうか悩むのは、今までに出てきたせんべいより大きい場合だけで良い。よって残りn枚の状況であれば、今までに出てきたせんべいよりも大きいせんべいが出る確率は、 1.0 / (N - n + 1) である。
今まで見た中で最大のせんべいが登場した時に、食べるか食べないかを分岐して再帰的に求めれば良い。
コード
#include <bits/stdc++.h> using namespace std; vector<vector<double>> dp; int N, K; double f(int n, int k) { if (dp[n][k] >= 0) return dp[n][k]; // 残り n 枚の中から k 枚を食べるという状況で、 // 今まで出てきたせんべいよりも大きなせんべいがこのターンに登場する確率 double pn = 1.0 / (N - n + 1); // このターンのせんべいを食べた時にそれが最大のせんべいを得られる確率 double np = 1.0 / N + pn * f(n - 1, k - 1) + (1 - pn) * f(n - 1, k); // このターンの煎餅をスルーした時に最大のせんべいを食べられる確率 double through = f(n - 1, k); dp[n][k] = max(np, through); return dp[n][k]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; dp.assign(N + 1, vector<double>(N + 1, -1)); for (int i = 0; i <= N; ++i) { dp[i][i] = 1.0 * i / N; dp[i][0] = 0; } cout << f(N, K) << endl; }