結果

問題 No.3079 Unite Japanese Prefectures
ユーザー navel_tos
提出日時 2025-04-04 23:59:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,953 ms / 4,000 ms
コード長 2,435 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 247,884 KB
最終ジャッジ日時 2025-04-05 00:00:11
合計ジャッジ時間 23,911 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3079 Unite Japanese Prefectures

#入力受取
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]

#コストに対する最小全域木を作成
class UnionFind:
    def __init__(self, N):
        self._parent = [-1] * N
    def find(self, Vi):
        stack = [Vi]
        while self._parent[ stack[-1] ] >= 0:
            stack.append( self._parent[ stack[-1] ] )
        p = stack.pop()
        while stack: self._parent[ stack.pop() ] = p
        return p
    def unite(self, Ui, Vi):
        Ui, Vi = self.find(Ui), self.find(Vi)
        if Ui == Vi: return False
        if self.size(Ui) < self.size(Vi):
            Ui, Vi = Vi, Ui
        self._parent[Ui] += self._parent[Vi]
        self._parent[Vi] = Ui
        return True
    def same(self, Ui, Vi):
        return self.find(Ui) == self.find(Vi)
    def size(self, Vi):
        return - self._parent[ self.find(Vi) ]

E = sorted([(Ci - 1, Ui - 1, Vi - 1) for Ui, Vi, Ci in edges])
UF = UnionFind(N)
F = [0] * 6
for Ci, Ui, Vi in E:
    if not UF.same(Ui, Vi):
        F[Ci] += 1
        assert UF.unite(Ui, Vi)
assert UF.size(0) == N and all(UF.same(0, i) for i in range(N))

#2. sushi DP  面倒なので連想配列で
#DP[S]: 状態Sから(0, 0, ･･･, 0)にするための操作回数の期待値
DP = {(0, 0, 0, 0, 0, 0): 0.0}
stack = [(0, tuple(F))]
while stack:
    f, S = stack.pop()
    if f >= 0:  #入りがけの処理
        if S in DP:
            continue
        stack.append((~ f, S))
        T = list(S)
        i = 5
        for d in range(5, -1, -1):  #次に出る目
            if i > d: i = d
            while i >= 0 and T[i] == 0:
                i -= 1
            if i < 0:
                continue
            T[i] -= 1
            if ( U := tuple(T) ) not in DP:
                stack.append((f, U))
            T[i] += 1

    else:  #帰りがけの処理
        T = list(S)
        fail = 0
        cnt = 0.0
        i = 5
        for d in range(5, -1, -1):
            if i > d: i = d
            while i >= 0 and T[i] == 0:
                i -= 1
            if i < 0:
                fail += 1
                continue
            T[i] -= 1
            assert ( U := tuple(T) ) in DP
            cnt += DP[U]
            T[i] += 1

        #DP[S] = 1 + (cnt + fail * DP[S]) / 6
        #(6 - fail) * DP[S] = 6 + cnt
        DP[S] = (6.0 + cnt) / (6 - fail)

print(DP[tuple(F)])
0