結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
|
提出日時 | 2022-03-31 21:42:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,245 ms / 5,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 448,640 KB |
最終ジャッジ日時 | 2024-11-17 13:55:33 |
合計ジャッジ時間 | 31,668 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
N = int(input()) A = list(map(int,input().split())) """ import sys sys.setrecursionlimit(10 ** 8) from functools import lru_cache @lru_cache(maxsize = 1000) def calc(a,b,c): if a == 0 and b == 0 and c == 0:return 0 u =a + b + c tmp = 0 if a != 0: tmp += calc(a-1,b,c) * a if b != 0: tmp += calc(a+1,b-1,c) * b if c != 0: tmp += calc(a,b+1,c-1) * c tmp = (tmp + N) / u return tmp a = 0 b = 0 c = 0 for i in A: if i == 0:c += 1 elif i == 1:b += 1 elif i == 2:a += 1 print(calc(a,b,c)) """ C = 3 * N + 1 dp = [[[0] * C for _ in range(C)] for _ in range(C)] for c in range(C): for b in range(C): for a in range(C): if a == 0 and b == 0 and c == 0:continue tmp = 0 if a != 0: tmp += dp[a-1][b][c] * a if b != 0 and a < C - 1: tmp += dp[a+1][b-1][c] * b if c != 0 and b < C - 1: tmp += dp[a][b+1][c-1] * c tmp = (tmp + N) / (a + b + c) dp[a][b][c] = tmp a = 0 b = 0 c = 0 for i in A: if i == 0:c += 1 elif i == 1:b += 1 elif i == 2:a += 1 print(dp[a][b][c])