結果

問題 No.108 トリプルカードコンプ
コンテスト
ユーザー Kyutatsu
提出日時 2025-09-15 22:16:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 1,139 bytes
コンパイル時間 1,395 ms
コンパイル使用メモリ 119,368 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2025-09-15 22:16:05
合計ジャッジ時間 2,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#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])]++;
    for (int i=3;0<i;i--) cnt[i-1] += cnt[i];
    

    // DP[1枚以上][2枚以上][3枚以上] := コンプまでの回数期待値

    vector DP(N+1, vector(N+1, vector(N+1, -1.0)));
    function<double(int,int,int)> dfs = [&](int n1, int n2, int n3) {
        if (DP[n1][n2][n3]!=-1.0) 
            return DP[n1][n2][n3];
        if (n3==N) return 0.0;
        
        double E = 1.0;    
        double N0 = N-n1;
        if (0<N0) 
            E += (N0 / N) * dfs(n1+1, n2, n3);
        
        double N1 = n1-n2;
        if (0<N1)
            E += (N1 / N) * dfs(n1, n2+1, n3);

        double N2 = n2-n3;
        if (0<N2)
            E += (N2 / N) * dfs(n1, n2, n3+1);

        double N3 = n3;
        E /= 1.0 - (N3 / N);
        
        DP[n1][n2][n3] = E;
        return E;
    };


    cout << fixed << setprecision(12) << dfs(cnt[1],cnt[2],cnt[3]) << endl;
}
0