結果

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

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<iomanip>
#include<functional>

using namespace std;

int main() {
    // DP[0枚コンプ][1枚コンプ][2枚コンプ] := その状態からコンプまで後何枚？
    // DP[0][0][0] = 0 -> 全て3枚コンプなので.

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

    double p = 1.0 / N;

    vector DP(N+1, vector(N+1, vector<double>(N+1, -1)));
    function<double(int,int,int)> dfs = [&](int a, int b, int c) {
        // 揃ってるのでコンプまで後0枚.
        if (a==0 && b==0 && c==0) return DP[a][b][c]= 0; 

        if (-1<DP[a][b][c]) return DP[a][b][c];

        int cnt3 = N - a - b - c;
        double E = 1.0;

        // 0枚所持 -> 1枚所持
        if (0<a) 
            E += p*a * dfs(a-1, b+1, c);

        // 1枚所持 -> 2枚所持
        if (0<b)
            E += p*b * dfs(a, b-1, c+1);

        // 2枚所持 -> 3枚所持
        if (0<c)
            E += p*c * dfs(a, b, c-1);

        // ダブり. 3枚以上所持 -> 3枚以上所持
        if (0<cnt3)
            E /= 1.0 - p*cnt3;
        return DP[a][b][c] = E;
    };
    cout << fixed << setprecision(12) << dfs(cnt[0], cnt[1], cnt[2]) << endl;

}
0