結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
|
提出日時 | 2020-04-02 22:23:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 5,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 1,485 ms |
コンパイル使用メモリ | 167,480 KB |
実行使用メモリ | 14,144 KB |
最終ジャッジ日時 | 2024-06-28 15:20:58 |
合計ジャッジ時間 | 2,695 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> P; typedef pair<ll,ll> l_l; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<P> vp; #define fi first #define se second #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) const int INF=1001001000; const int mINF=-1001001000; const ll LINF=1010010010010010000; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //グリッド:(典型)dp,dfs,bfs,最短経路,その他 int cnt[4]; int n,a; double dp[110][110][110]; double dfs(int x,int y,int z){ if(dp[x][y][z]>=0) return dp[x][y][z]; dp[x][y][z]=n*1.0/(x+y+z); if(x>0) dp[x][y][z]+=dfs(x-1,y,z)*x/(x+y+z); if(y>0) dp[x][y][z]+=dfs(x+1,y-1,z)*y/(x+y+z); if(z>0) dp[x][y][z]+=dfs(x,y+1,z-1)*z/(x+y+z); return dp[x][y][z]; } int main(){ cin>>n; rep(i,110){ rep(j,110){ rep(k,110){ dp[i][j][k]=-1; } } } rep(i,n){ cin>>a; if(a==0) cnt[3]++; else if(a==1) cnt[2]++; else if(a==2) cnt[1]++; } dp[0][0][0]=0.0; cout <<fixed<<setprecision(10); cout << dfs(cnt[1],cnt[2],cnt[3]) << endl; return 0; }