結果

問題 No.108 トリプルカードコンプ
ユーザー codershifthcodershifth
提出日時 2015-08-13 01:01:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 2,996 bytes
コンパイル時間 1,285 ms
コンパイル使用メモリ 151,092 KB
実行使用メモリ 11,152 KB
最終ジャッジ日時 2023-09-25 08:36:12
合計ジャッジ時間 2,629 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
10,952 KB
testcase_01 AC 5 ms
10,832 KB
testcase_02 AC 5 ms
10,852 KB
testcase_03 AC 5 ms
10,964 KB
testcase_04 AC 5 ms
11,084 KB
testcase_05 AC 5 ms
10,828 KB
testcase_06 AC 5 ms
10,864 KB
testcase_07 AC 10 ms
10,924 KB
testcase_08 AC 5 ms
10,948 KB
testcase_09 AC 5 ms
10,860 KB
testcase_10 AC 5 ms
10,828 KB
testcase_11 AC 5 ms
10,832 KB
testcase_12 AC 5 ms
10,828 KB
testcase_13 AC 5 ms
10,824 KB
testcase_14 AC 5 ms
11,044 KB
testcase_15 AC 5 ms
10,836 KB
testcase_16 AC 5 ms
10,952 KB
testcase_17 AC 5 ms
11,012 KB
testcase_18 AC 9 ms
11,024 KB
testcase_19 AC 6 ms
10,828 KB
testcase_20 AC 6 ms
11,152 KB
testcase_21 AC 7 ms
11,044 KB
testcase_22 AC 5 ms
11,084 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

class TripleCardComplete {
public:
    //
    // カード枚数が 0 枚, 1 枚, 2 枚のカードの種類数を状態としてもつ DP でやる
    //
    // +-> Exp[a][b][c] -a のうちどれかが出る-> Exp[a-1][b+1][c]
    // |    |    |
    // |    |    +-------b のうちどれかが出る-> Exp[a][b-1][c+1]
    // +----+    |
    //           +-------c のうちどれかが出る-> Exp[a][b][c-1]
    //

    int N;
    // 時間・空間計算量 O(10^6)
    double memo[101][101][101];

    // カード枚数が 0 枚のものが a 種類残っている
    // カード枚数が 1 枚のものが b 種類残っている
    // カード枚数が 2 枚のものが c 種類残っている
    // ときからスタートしたときのカードをコンプリートするまで買うカードの期待値
    double calc(int a, int b, int c) {
            if (memo[a][b][c] >= 0) // すでに計算済み
                return memo[a][b][c];

            double res = 0.0;
            int total = a+b+c;

            if (total == 0) // 全て手に入った
                return memo[a][b][c] = 0.0;

            // a,b,c に含まれるカードたちのどれかが出る確率
            double p = (double)total/N;
            double q = 1.0/p;

            // 結局自分自身から他へ遷移しないケース
            // a,b,c に含まれるカードたちが出る確率は p だった。
            // これら以外が出るまでの試行回数の期待値は 1/p なのでこれを加える。
            res += q;

            // 自己ループを複数回くりかえしてから別状態への遷移がある場合もあるので q 掛ける
            if (a) res += calc(a-1,b+1,c) * (double)a/N * q; // a のうちどれかが出るときの遷移
            if (b) res += calc(a,b-1,c+1) * (double)b/N * q; // b のうちどれかが出るときの遷移
            if (c) res += calc(a,b,c-1)   * (double)c/N * q; // c のうちどれかが出るときの遷移

            return memo[a][b][c] = res;
    }
    void solve(void) {
            cin>>N;
            vector<int> A(N);

            REP(i,101)
            REP(j,101)
            REP(k,101)
                memo[i][j][k] = -1;

            int n[3] = {0,0,0}; // n[i] := はじめに持っているカード枚数が i 枚のカードの種類総数
            REP(i,N)
            {
                cin>>A[i];
                if (A[i] < 3)
                    ++n[A[i]];
            }
            cout<<setprecision(20)<<calc(n[0],n[1],n[2])<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TripleCardComplete();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0