結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
|
提出日時 | 2020-04-08 22:56:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 1,073 bytes |
コンパイル時間 | 1,567 ms |
コンパイル使用メモリ | 166,628 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-07-19 05:47:54 |
合計ジャッジ時間 | 2,386 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; int n; double dp[110][110][110]; int cnt[4]; double rec(int x,int y,int z) {//x一枚以上あるカードの種類 //y二枚以上あるカードの種類 //z三枚以上あるカードの種類 //それからコンプリートするために必要な回数の期待値 if(dp[x][y][z]!=-1)return dp[x][y][z]; dp[x][y][z] = 0; //z/nででないとき、でるまでの回数の期待値 double exp_num = 1.0 * n/(n-z); //n-x ゼロ枚の数 if(x!=n)dp[x][y][z] += (rec(x+1,y,z)+exp_num)*(n-x)/(n-z); //x-y一枚のすう if(y!=x)dp[x][y][z] += (rec(x,y+1,z)+exp_num)*(x-y)/(n-z); //y−z 二枚のすう if(z!=y)dp[x][y][z] += (rec(x,y,z+1)+exp_num)*(y-z)/(n-z); return dp[x][y][z]; } int main() { cin >> n; for(int i = 0;i<n+1;i++)for(int j = 0;j<n+1;++j)for(int k = 0;k <n+1;k++)dp[i][j][k] = -1; dp[n][n][n] = 0; for(int i = 0;i<n;i++) { int x; cin >> x; cnt[min(x,3)]++; } cnt[2] += cnt[3]; cnt[1] += cnt[2]; printf("%.12lf\n",rec(cnt[1],cnt[2],cnt[3])); return 0; }