Baby Stepsなブログ

競プロとか。間違ったこと書いてあったら@pi0nep1oneにご連絡ください。

EDPC J - Sushi

atcoder.jp

期待値DPの問題
難しかったので、要復習としてメモ.

実装は以下の記事を参考にほぼ写経させていただきました.

www.hamayanhamayan.com

qiita.com

実装

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

#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;

// dp[c1][c2][c3] := 1個残りがc1個, 2個残りがc2個, 3個残りがc3個である状態にするまでの操作回数の期待値

int N, A[303], C[4];
double dp[303][303][303];

signed main() {
  cin >> N;
  rep(i, 0, N) cin >> A[i];
  rep(i, 0, N) C[A[i]]++;

  rep(c3, 0, N + 1) rep(c2, 0, N + 1) rep(c1, 0, N + 1) {
      int sm = c1 + c2 + c3;
      if (sm == 0) continue;

      dp[c1][c2][c3] = 1.0 * N / sm;
      if (c1) dp[c1][c2][c3] += dp[c1 - 1][c2][c3] * c1 / sm;
      if (c2) dp[c1][c2][c3] += dp[c1 + 1][c2 - 1][c3] * c2 / sm;
      if (c3) dp[c1][c2][c3] += dp[c1][c2 + 1][c3 - 1] * c3 / sm;
  }

  coutd(dp[C[1]][C[2]][C[3]]);
}