結果

問題 No.108 トリプルカードコンプ
ユーザー data9824data9824
提出日時 2015-06-25 12:35:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 1,549 bytes
コンパイル時間 590 ms
コンパイル使用メモリ 75,612 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-07-07 17:32:55
合計ジャッジ時間 1,301 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
11,616 KB
testcase_01 AC 3 ms
11,648 KB
testcase_02 AC 3 ms
11,648 KB
testcase_03 AC 3 ms
11,656 KB
testcase_04 AC 3 ms
11,520 KB
testcase_05 AC 3 ms
11,492 KB
testcase_06 AC 3 ms
11,568 KB
testcase_07 AC 8 ms
11,648 KB
testcase_08 AC 3 ms
11,520 KB
testcase_09 AC 4 ms
11,492 KB
testcase_10 AC 3 ms
11,392 KB
testcase_11 AC 3 ms
11,648 KB
testcase_12 AC 3 ms
11,520 KB
testcase_13 AC 3 ms
11,776 KB
testcase_14 AC 3 ms
11,744 KB
testcase_15 AC 3 ms
11,648 KB
testcase_16 AC 3 ms
11,540 KB
testcase_17 AC 4 ms
11,520 KB
testcase_18 AC 6 ms
11,520 KB
testcase_19 AC 4 ms
11,648 KB
testcase_20 AC 3 ms
11,520 KB
testcase_21 AC 5 ms
11,520 KB
testcase_22 AC 3 ms
11,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 (!std::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