結果

問題 No.108 トリプルカードコンプ
コンテスト
ユーザー codershifth
提出日時 2015-08-13 01:01:37
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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