EDPC J - Sushi
期待値DPの問題
難しかったので、要復習としてメモ.
実装は以下の記事を参考にほぼ写経させていただきました.
実装
#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]]); }