SRM466 Div1 Medium

500

5箇所を選ぶパターン数を数える。
DP[何列目まで決めた][残り何箇所][勝利状態かどうか] = パターン数

dp[N][0][true] / (dp[N][0][true] + dp[N][0][false])
で確率が出る。

class LotteryPyaterochka {
public:
  double chanceToWin(int N)
  {
    const int M = 5;
    int p[M];
    fill(p, p + M, 0);
    for (int bit = 0; bit < (1 << M); ++bit) {
      int cnt = 0;
      for (int i = 0; i < M; ++i) {
        if (bit & (1 << i)) ++cnt;
      }
      ++p[cnt];
    }

    const int C = 5 + 1;
    double dp[N + 1][C][2];
    fill(&dp[0][0][0], &dp[N][C - 1][2 - 1] + 1, 0);
    dp[0][5][0] = 1;

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < C; ++j) {
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l <= j; ++l) {
            dp[i + 1][j - l][k  || (3 <= l)] += dp[i][j][k] * p[l];
          }
        }
      }
    }

    return dp[N][0][true] / (dp[N][0][true] + dp[N][0][false]);
  }
}