結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
![]() |
提出日時 | 2022-07-28 03:09:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,105 ms / 5,000 ms |
コード長 | 1,731 bytes |
コンパイル時間 | 490 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 39,424 KB |
最終ジャッジ日時 | 2024-07-17 17:11:34 |
合計ジャッジ時間 | 6,858 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
N=int(input()) A=list(map(int,input().split())) X=[0,0,0,0] for a in A: X[min(3,a)]+=1 DP=[[[0]*(N+1) for i in range(N+1)] for j in range(N+1)] P=[[[0]*(N+1) for i in range(N+1)] for j in range(N+1)] DP[X[0]][X[1]][X[2]]=0 P[X[0]][X[1]][X[2]]=1 for rest in range(N,-1,-1): for i in range(N,-1,-1): for j in range(N,-1,-1): k=rest-i-j if k<0: continue if P[i][j][k]<=0: continue if i>0: if P[i-1][j+1][k]==0: P[i-1][j+1][k]=P[i][j][k]*i/(i+j+k) DP[i-1][j+1][k]=DP[i][j][k]+N/(i+j+k) else: xx=P[i-1][j+1][k] yy=P[i][j][k]*i/(i+j+k) DP[i-1][j+1][k]=(xx*DP[i-1][j+1][k]+yy*(DP[i][j][k]+N/(i+j+k)))/(xx+yy) P[i-1][j+1][k]+=yy if j>0: if P[i][j-1][k+1]==0: P[i][j-1][k+1]=P[i][j][k]*j/(i+j+k) DP[i][j-1][k+1]=DP[i][j][k]+N/(i+j+k) else: xx=P[i][j-1][k+1] yy=P[i][j][k]*j/(i+j+k) DP[i][j-1][k+1]=(xx*DP[i][j-1][k+1]+yy*(DP[i][j][k]+N/(i+j+k)))/(xx+yy) P[i][j-1][k+1]+=yy if k>0: if P[i][j][k-1]==0: P[i][j][k-1]=P[i][j][k]*k/(i+j+k) DP[i][j][k-1]=DP[i][j][k]+N/(i+j+k) else: xx=P[i][j][k-1] yy=P[i][j][k]*k/(i+j+k) DP[i][j][k-1]=(xx*DP[i][j][k-1]+yy*(DP[i][j][k]+N/(i+j+k)))/(xx+yy) P[i][j][k-1]+=yy print(DP[0][0][0])