結果
問題 | No.108 トリプルカードコンプ |
ユーザー |
|
提出日時 | 2021-11-04 23:17:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 151 ms / 5,000 ms |
コード長 | 1,202 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 97,792 KB |
最終ジャッジ日時 | 2024-10-15 05:50:45 |
合計ジャッジ時間 | 3,321 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import sys sys.setrecursionlimit(10**7) N = int(input()) A = list(map(int,input().split())) dp = [[[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] memo = [[[False for _ in range(N+1)] for _ in range(101)] for _ in range(101)] memo[N][N][N] = True def DP(x,y,z): if x == N and y == N and z == N: return if x >= y >= z: pass else: return if x + 1 <= N: if memo[x+1][y][z]: dp[x][y][z] += (N-x) * (dp[x+1][y][z]) else: DP(x+1,y,z) dp[x][y][z] += (N-x) * (dp[x+1][y][z]) if y + 1 <= N: if memo[x][y+1][z]: dp[x][y][z] += (x-y) * (dp[x][y+1][z]) else: DP(x,y+1,z) dp[x][y][z] += (x-y) * (dp[x][y+1][z]) if z + 1 <= N: if memo[x][y][z+1]: dp[x][y][z] += (y-z) * (dp[x][y][z+1]) else: DP(x,y,z+1) dp[x][y][z] += (y-z) * (dp[x][y][z+1]) dp[x][y][z] += N dp[x][y][z] /= N -z memo[x][y][z] = True x = 0 y = 0 z = 0 for i in range(N): if A[i] >= 1: x += 1 if A[i] >= 2: y += 1 if A[i] >= 3: z += 1 DP(x,y,z) print(dp[x][y][z])