読者です 読者をやめる 読者になる 読者になる

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;
}