結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
![]() |
提出日時 | 2023-01-16 21:11:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 3,763 ms |
コンパイル使用メモリ | 261,420 KB |
最終ジャッジ日時 | 2025-02-10 03:55:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ld pie=3.14159265359; ll mod=998244353; ll inf=99999999999999999; vector<vector<vector<ld>>>dp; ll n; ll one=0,two=0,thr=0; ld saiki(ll a,ll b,ll c){ if (a+b+c>n||a<0||b<0) { return 0; } if (dp[a][b][c]!=-1) { return dp[a][b][c]; } ld pl=(ld)n/(ld)(n-c); ld y=0; y+=(saiki(a+1,b,c)+pl)*((ld)(n-a-b-c)/(ld)(n-c)); y+=(saiki(a-1,b+1,c)+pl)*((ld)(a)/(ld)(n-c)); y+=(saiki(a,b-1,c+1)+pl)*((ld)(b)/(ld)(n-c)); dp[a][b][c]=y; return dp[a][b][c]; } int main(){ cin >> n; vector<ll>a(n); for (ll i = 0; i < n; i++) { cin >> a[i]; } ll one=0,two=0,thr=0; for (ll i = 0; i < n; i++) { if (a[i]==1) { one+=1; } if (a[i]==2) { two+=1; } if (a[i]>=3) { thr+=1; } } dp.assign(n+1,vector<vector<ld>>(n+1,vector<ld>(n+1,-1))); dp[0][0][n]=0; cout << setprecision(20) << saiki(one,two,thr) << endl; }