結果

問題 No.108 トリプルカードコンプ
コンテスト
ユーザー kusainu7
提出日時 2021-05-29 19:08:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 705 bytes
コンパイル時間 535 ms
コンパイル使用メモリ 67,720 KB
最終ジャッジ日時 2025-01-21 20:36:31
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
using namespace std;

double c[110][110][110] = {};

void dp(int n, int *a) {
	c[n][n][n] = 0;
	for (int i=n; i>=0; i--) {
		for (int j=n; j>=0; j--) {
			for (int k=n; k>=0; k--) {
				if (k>=n) {
					continue;
				}
				c[i][j][k] = 1.0*n/(n-k);
				if (i!=n) c[i][j][k] += c[i+1][j][k]*(n-i)/(n-k);
				if (i!=j) c[i][j][k] += c[i][j+1][k]*(i-j)/(n-k);
				if (j!=k) c[i][j][k] += c[i][j][k+1]*(j-k)/(n-k);
			}
		}
	}
}

int main() {
	int n, x;
	cin >> n;
	int a[4] = {};

	for (int i=0; i<n; i++) {
		cin >> x;
		if (x>3) {
			a[3]++;
		} else if (x!=0) {
			a[x]++;
		}
	}
	
	for (int i=2; i>0; i--) {
		a[i] += a[i+1];
	}
	
	dp(n, a);

	printf("%.10f\n", c[a[1]][a[2]][a[3]]);
}
0