結果

問題 No.108 トリプルカードコンプ
コンテスト
ユーザー data9824
提出日時 2015-06-25 12:27:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 7 ms / 5,000 ms
コード長 1,544 bytes
コンパイル時間 565 ms
コンパイル使用メモリ 75,616 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-07-07 17:32:44
合計ジャッジ時間 1,463 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <limits>
#include <cmath>

using namespace std;

int n;
double cache[101][101][101];

// カードの現在枚数が?であるカードがm?種類の時、
// あと何枚引く必要があるか。
double expected(int m0, int m1, int m2) {
	if (!isnan(cache[m0][m1][m2])) {
		return cache[m0][m1][m2];
	}
	if (m0 == 0 && m1 == 0 && m2 == 0) {
		cache[m0][m1][m2] = 0;
		return 0;
	}
	/*
		E(a,b,c) = (1+E(a-1,b+1,c))*a/N + (1+E(a,b-1,c+1))*b/N + (1+E(a,b,c-1))*c/N + (1+E(a,b,c))*(N-a-b-c)/N
		E(a,b,c) = 1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N + E(a, b, c)*(N-a-b-c)/N
		E(a,b,c)(1 - (N-a-b-c)/N) = (1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N)
		E(a,b,c) = (1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N) * N/(a+b+c)
	*/
	double result = 1;
	if (m0 > 0) {
		result += expected(m0 - 1, m1 + 1, m2) * m0 / n;
	}
	if (m1 > 0) {
		result += expected(m0, m1 - 1, m2 + 1) * m1 / n;
	}
	if (m2 > 0) {
		result += expected(m0, m1, m2 - 1) * m2 / n;
	}
	result *= (double)n / (m0 + m1 + m2);
	cache[m0][m1][m2] = result;
	return result;
}

int main() {
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int m[3] = { 0 };
	for (int i = 0; i < n; ++i) {
		if (a[i] <= 2) {
			++m[a[i]];
		}
	}
	fill(&cache[0][0][0], &cache[100][100][100] + 1, numeric_limits<double>::quiet_NaN());
	double result = expected(m[0], m[1], m[2]);
	cout << fixed << setprecision(12) << result << endl;
	return 0;
}
0