結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
|
提出日時 | 2023-06-26 13:53:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,236 bytes |
コンパイル時間 | 516 ms |
コンパイル使用メモリ | 70,400 KB |
実行使用メモリ | 13,920 KB |
最終ジャッジ日時 | 2024-07-03 09:00:08 |
合計ジャッジ時間 | 1,879 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <iostream> #include <cmath> #include <math.h> /** 8 3 4 5 6 7 8 9 10 */ int N; double dp[110][110][110]; int cnt[4]; double solve(int x, int y, int z) { // memoization if (dp[x][y][z] != -1) return dp[x][y][z]; dp[x][y][z] = 0; // 2枚以下しかもっていないものが出るまで // 引く回数の期待値 double exp_num = 1.0 * N / (N - z); // (条件付き期待値) * (条件付き確率) の足しあわせ if (x != N) { double d = solve(x+1, y, z); dp[x][y][z] += (d + exp_num) * (N - x) / (N - z); } if (y != x) { double d = solve(x, y+1, z); dp[x][y][z] += (d + exp_num) * (x - y) / (N - z); } if (z != y) { double d = solve(x, y, z+1); dp[x][y][z] += (d + exp_num) * (y - z) / (N - z); } return dp[x][y][z]; } int main() { std::cin >> N; for (int i = 0; i <= N; i++) { for (int j = 0; j <= N; j++) { for (int k = 0; k <= N; k++) { dp[i][j][k] = -1; } } } dp[N][N][N] = 0; for (int i = 0; i < N; i++) { int A; std::cin >> A; cnt[std::min(A, 3)]++; } for (int i = 2; i > 0; i--) { cnt[i] += cnt[i + 1]; } double doub = solve(cnt[1], cnt[2], cnt[3]); printf("%.12f\n", doub); return 0; }