結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
|
提出日時 | 2015-01-18 12:40:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 842 ms |
コンパイル使用メモリ | 102,904 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-06-22 19:05:21 |
合計ジャッジ時間 | 1,771 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> using namespace std; vector<vector<vector<double> > > memo; double solve(int n, int a, int b, int c) { if(a == 0 && b == 0 && c == 0) return 0.0; if(a < 0 || b < 0 || c < 0) return 0.0; if(memo[a][b][c] > -0.5) return memo[a][b][c]; double ret = solve(n, a-1, b, c) * a / n + solve(n, a+1, b-1, c) * b / n + solve(n, a, b+1, c-1) * c / n + 1; ret *= n / (double)(a + b + c); return memo[a][b][c] = ret; } int main() { int n; cin >> n; vector<int> init(11); for(int i=0; i<n; ++i){ int a; cin >> a; ++ init[a]; } memo.assign(n+1, vector<vector<double> >(n+1, vector<double>(n+1, -1.0))); double ret = solve(n, init[2], init[1], init[0]); printf("%.10f\n", ret); return 0; }