結果
問題 | No.108 トリプルカードコンプ |
ユーザー |
|
提出日時 | 2023-06-26 14:02:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,228 bytes |
コンパイル時間 | 526 ms |
コンパイル使用メモリ | 69,192 KB |
実行使用メモリ | 13,276 KB |
最終ジャッジ日時 | 2024-07-03 09:10:02 |
合計ジャッジ時間 | 1,347 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 3 WA * 17 |
ソースコード
#include <iostream>#include <cmath>#include <math.h>/**83 4 5 6 7 8 9 10*/int N;double dp[110][110][110];int cnt[3];double solve(int x, int y, int z) {// memoizationif (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;if (A >= 3) A = 2;cnt[A - 1]++;}cnt[1] += cnt[2];cnt[0] += cnt[2];double doub = solve(cnt[0], cnt[1], cnt[2]);printf("%.12f\n", doub);return 0;}