結果

問題 No.108 トリプルカードコンプ
ユーザー codershifthcodershifth
提出日時 2015-08-13 01:01:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 2,996 bytes
コンパイル時間 1,437 ms
コンパイル使用メモリ 165,200 KB
実行使用メモリ 11,624 KB
最終ジャッジ日時 2024-07-18 07:03:25
合計ジャッジ時間 2,229 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,572 KB
testcase_01 AC 4 ms
11,504 KB
testcase_02 AC 4 ms
11,516 KB
testcase_03 AC 4 ms
11,484 KB
testcase_04 AC 3 ms
11,272 KB
testcase_05 AC 4 ms
11,392 KB
testcase_06 AC 4 ms
11,336 KB
testcase_07 AC 8 ms
11,624 KB
testcase_08 AC 4 ms
11,548 KB
testcase_09 AC 3 ms
11,276 KB
testcase_10 AC 3 ms
11,548 KB
testcase_11 AC 4 ms
11,568 KB
testcase_12 AC 4 ms
11,396 KB
testcase_13 AC 5 ms
11,496 KB
testcase_14 AC 5 ms
11,344 KB
testcase_15 AC 4 ms
11,396 KB
testcase_16 AC 4 ms
11,460 KB
testcase_17 AC 3 ms
11,276 KB
testcase_18 AC 6 ms
11,388 KB
testcase_19 AC 5 ms
11,396 KB
testcase_20 AC 4 ms
11,336 KB
testcase_21 AC 5 ms
11,396 KB
testcase_22 AC 4 ms
11,396 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