結果

問題 No.108 トリプルカードコンプ
ユーザー KyutatsuKyutatsu
提出日時 2024-12-31 00:17:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,379 bytes
コンパイル時間 5,320 ms
コンパイル使用メモリ 285,180 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2024-12-31 00:17:41
合計ジャッジ時間 5,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 16 ms
11,904 KB
testcase_08 AC 9 ms
11,904 KB
testcase_09 AC 9 ms
12,032 KB
testcase_10 AC 9 ms
11,904 KB
testcase_11 AC 9 ms
11,904 KB
testcase_12 WA -
testcase_13 AC 3 ms
6,820 KB
testcase_14 AC 3 ms
6,820 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 3 ms
6,816 KB
testcase_18 AC 12 ms
10,880 KB
testcase_19 AC 9 ms
10,624 KB
testcase_20 AC 9 ms
11,776 KB
testcase_21 AC 13 ms
11,648 KB
testcase_22 AC 8 ms
10,880 KB
権限があれば一括ダウンロードができます

ソースコード

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 << dfs(cnt[1], cnt[2], cnt[3]) << endl;

}
0