結果

問題 No.3079 Unite Japanese Prefectures
コンテスト
ユーザー navel_tos
提出日時 2025-04-05 00:13:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,247 ms / 4,000 ms
コード長 2,673 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 150,384 KB
最終ジャッジ日時 2025-04-05 00:14:05
合計ジャッジ時間 17,649 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)にするための操作回数の期待値
powN = [pow(N, i) for i in range(6)]
def convert(S): return sum(S[i] * powN[i] for i in range(6))
def rev(X):
    S = [0] * 6
    for i in range(6): S[i] = X % N; X //= N
    return S
DP = {0: 0.0, convert(F): -1}
stack = [convert(F)]
while stack:
    X = stack.pop()
    if X >= 0:  #入りがけの処理
        if DP[X] != -1:
            continue
        stack.append(~ X)
        T = rev(X)
        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 ( Y := convert(T) ) not in DP:
                DP[Y] = -1
                stack.append(Y)
            T[i] += 1

    else:  #帰りがけの処理
        assert DP[X := ~ X] == -1
        T = rev(X)
        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 ( Y := convert(T) ) in DP
            cnt += DP[Y]
            T[i] += 1

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

print(DP[ convert(F) ])
0