結果

問題 No.108 トリプルカードコンプ
ユーザー Kyutatsu
提出日時 2024-12-31 00:18:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 1,409 bytes
コンパイル時間 4,862 ms
コンパイル使用メモリ 285,932 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-12-31 00:18:20
合計ジャッジ時間 5,002 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
#include <functional>

using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N); 
    for (int i=0;i<N;i++) cin >> A[i];
    vector<int> cnt(4);
    for (int i=0;i<N;i++) cnt[min(3, A[i])]++;

    // i "以上" になるよう累積和
    for (int i=2;0<=i;i--) cnt[i] += cnt[i+1];


    // DP[x][y][z] := コンプまでの期待開封数
    vector DP(N+1, vector(N+1, vector<double>(N+1, -1)));
    DP[N][N][N] = 0;
    function<double(int,int,int)> dfs = [&](int x, int y, int z) {
        if (DP[x][y][z] != -1) return DP[x][y][z];

        DP[x][y][z] = 1.0;  // 今回開封

        double cnt0 = N - x;

        // 0 -> 1
        if (0 < cnt0) {  // dfsが走ると困るので ifを入れる.
            double p01 = cnt0 / N;
            DP[x][y][z] += dfs(x+1, y, z) * p01; 
        }

        // 1 -> 2
        if (0 < x - y) {
            double p12 = 1.0 * (x - y) / N;
            DP[x][y][z] += dfs(x, y+1, z) * p12;
        }

        // 2 -> 3
        if (0 < y - z) {
            double p23 = 1.0 * (y - z) / N;
            DP[x][y][z] += dfs(x, y, z+1) * p23;
        }

        // 3 -> 3
        if (0 < z) {
            double p33 = 1.0 * z / N;
            DP[x][y][z] /= (1.0 - p33);
        }

        return DP[x][y][z];
    };
    
cout << fixed << setprecision(16)
     << dfs(cnt[1], cnt[2], cnt[3]) << endl;

}
0