結果
問題 |
No.3079 Unite Japanese Prefectures
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:38:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 560 ms / 4,000 ms |
コード長 | 1,788 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 91,384 KB |
最終ジャッジ日時 | 2025-03-28 22:38:54 |
合計ジャッジ時間 | 7,205 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
class unif: def __init__(self,n): self.pare=[-1]*n self.size=[1]*n def root(self,x): while self.pare[x]!=-1: x=self.pare[x] return x def unite(self,u,v): rootu=self.root(u) rootv=self.root(v) if rootu!=rootv: if self.size[rootu]>=self.size[rootv]: self.pare[rootv]=rootu self.size[rootu]+=self.size[rootv] else: self.pare[rootu]=rootv self.size[rootv]+=self.size[rootu] def same(self,s,t): return self.root(s)==self.root(t) N,M=map(int,input().split()) u=[0]*7 L=[] Z=unif(N) for i in range(M): a,b,c=map(int,input().split()) L.append((c,a-1,b-1)) L.sort() for i in range(M): c,a,b=L[i][:] if Z.same(a,b)==False: u[c]+=1 Z.unite(a,b) R=[] for k in range(1,7): for i in range((u[k])): R.append(k) K=len(R) a,b,c,d,e,f=u[1],u[2],u[3],u[4],u[5],u[6] dp=[[[[[[0]*(f+1) for i in range(e+1)] for j in range(d+1)] for k in range(c+1)] for l in range(b+1)] for r in range(a+1)] for c1 in range(a+1): for c2 in range(b+1): for c3 in range(c+1): for c4 in range(d+1): for c5 in range(e+1): for c6 in range(f+1): v=[0,c1,c2,c3,c4,c5,c6] if sum(v)==0: continue w=1 t=0 for x in range(1,7): ans=False for y in range(x,0,-1): if v[y]==0: continue v2=v[:] v2[y]-=1 v2=v2[1:] z1,z2,z3,z4,z5,z6=v2[:] score=dp[z1][z2][z3][z4][z5][z6] w+=score/6 ans=True break if ans==False: t+=1/6 w/=1-t dp[c1][c2][c3][c4][c5][c6]=w print(dp[a][b][c][d][e][f])