結果
問題 | No.108 トリプルカードコンプ |
ユーザー | data9824 |
提出日時 | 2015-06-25 12:27:36 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 7 ms / 5,000 ms |
コード長 | 1,544 bytes |
コンパイル時間 | 565 ms |
コンパイル使用メモリ | 75,616 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-07-07 17:32:44 |
合計ジャッジ時間 | 1,463 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
11,776 KB |
testcase_01 | AC | 4 ms
11,520 KB |
testcase_02 | AC | 4 ms
11,640 KB |
testcase_03 | AC | 3 ms
11,524 KB |
testcase_04 | AC | 3 ms
11,520 KB |
testcase_05 | AC | 4 ms
11,748 KB |
testcase_06 | AC | 4 ms
11,520 KB |
testcase_07 | AC | 7 ms
11,648 KB |
testcase_08 | AC | 4 ms
11,648 KB |
testcase_09 | AC | 4 ms
11,776 KB |
testcase_10 | AC | 5 ms
11,648 KB |
testcase_11 | AC | 4 ms
11,684 KB |
testcase_12 | AC | 5 ms
11,520 KB |
testcase_13 | AC | 5 ms
11,520 KB |
testcase_14 | AC | 5 ms
11,644 KB |
testcase_15 | AC | 4 ms
11,648 KB |
testcase_16 | AC | 4 ms
11,592 KB |
testcase_17 | AC | 3 ms
11,672 KB |
testcase_18 | AC | 7 ms
11,520 KB |
testcase_19 | AC | 5 ms
11,648 KB |
testcase_20 | AC | 4 ms
11,648 KB |
testcase_21 | AC | 7 ms
11,528 KB |
testcase_22 | AC | 4 ms
11,520 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <limits> #include <cmath> using namespace std; int n; double cache[101][101][101]; // カードの現在枚数が?であるカードがm?種類の時、 // あと何枚引く必要があるか。 double expected(int m0, int m1, int m2) { if (!isnan(cache[m0][m1][m2])) { return cache[m0][m1][m2]; } if (m0 == 0 && m1 == 0 && m2 == 0) { cache[m0][m1][m2] = 0; return 0; } /* E(a,b,c) = (1+E(a-1,b+1,c))*a/N + (1+E(a,b-1,c+1))*b/N + (1+E(a,b,c-1))*c/N + (1+E(a,b,c))*(N-a-b-c)/N E(a,b,c) = 1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N + E(a, b, c)*(N-a-b-c)/N E(a,b,c)(1 - (N-a-b-c)/N) = (1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N) E(a,b,c) = (1 + E(a-1,b+1,c)*a/N + E(a,b-1,c+1)*b/N + E(a,b,c-1)*c/N) * N/(a+b+c) */ double result = 1; if (m0 > 0) { result += expected(m0 - 1, m1 + 1, m2) * m0 / n; } if (m1 > 0) { result += expected(m0, m1 - 1, m2 + 1) * m1 / n; } if (m2 > 0) { result += expected(m0, m1, m2 - 1) * m2 / n; } result *= (double)n / (m0 + m1 + m2); cache[m0][m1][m2] = result; return result; } int main() { cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } int m[3] = { 0 }; for (int i = 0; i < n; ++i) { if (a[i] <= 2) { ++m[a[i]]; } } fill(&cache[0][0][0], &cache[100][100][100] + 1, numeric_limits<double>::quiet_NaN()); double result = expected(m[0], m[1], m[2]); cout << fixed << setprecision(12) << result << endl; return 0; }