結果
問題 | 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>/**83 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) {// 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;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;}