結果

問題 No.108 トリプルカードコンプ
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-28 16:31:58
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 1,243 bytes
コンパイル時間 5,603 ms
コンパイル使用メモリ 206,208 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-08-28 16:32:05
合計ジャッジ時間 6,941 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2014/12/22/0900 より
import std;

// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}

void main()
{
	// 入力
	int N = readln.chomp.to!int;
	auto A = readln.split.to!(int[]);
	// 答えの計算
	// 3枚必要な種類数、2枚必要な種類数、1枚必要な種類数
	int cnt3, cnt2, cnt1;
	foreach (a; A) {
		switch (a) {
		case 0:
			++cnt3;
			break;
		case 1:
			++cnt2;
			break;
		case 2:
			++cnt1;
			break;
		default:
			break;
		}
	}
	auto memo = uninitializedArray!(double[][][])(N + 1, N + 1, N + 1);
	fill(memo, -1.0);
	memo[0][0][0] = 0;
	double dp(int n3, int n2, int n1)
	{
		if (memo[n3][n2][n1] >= 0) return memo[n3][n2][n1];

		memo[n3][n2][n1] = N * 1.0 / (n1 + n2 + n3);
		if (n1 > 0) memo[n3][n2][n1] += dp(n3, n2, n1 - 1) * n1 / (n1 + n2 + n3);
		if (n2 > 0) memo[n3][n2][n1] += dp(n3, n2 - 1, n1 + 1) * n2 / (n1 + n2 + n3);
		if (n3 > 0) memo[n3][n2][n1] += dp(n3 - 1, n2 + 1, n1) * n3 / (n1 + n2 + n3);
		return memo[n3][n2][n1];
	}
	// 答えの出力
	writefln("%.12f", dp(cnt3, cnt2, cnt1));
}
0