Day 022-Q5 | 確率的グラフ問題（Hitting Time）

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられる。各頂点 $v$ には次数 $\deg(v)$ があり、ランダムウォークでは現在の頂点から一様ランダムに隣接頂点を選んで移動する。

$Q$ 個のクエリに答えよ。各クエリは s t: 頂点 $s$ から出発して初めて頂点 $t$ に到達するまでの期待ステップ数を答えよ（$\bmod 10^9 + 7$）。グラフは連結であることが保証される。

入力形式

N M
u_1 v_1
u_2 v_2
...
u_M v_M
Q
s_1 t_1
...
s_Q t_Q

制約

$2 \leq N \leq 500$

$1 \leq M \leq N(N-1)/2$

$1 \leq Q \leq 10^5$

クエリの $s \neq t$, グラフは連結

入出力例

入力例 1

出力例 1

4頂点の環グラフ。$H(1 \to 2) = 1$（直接隣接）、$H(1 \to 3) = 4$（対角）、$H(1 \to 4) = 3$（逆回り）。

ヒント (段階的開示)

ヒント1: 方向性

Hitting Time（初到達時間の期待値）は連立方程式を解く問題。頂点 $t$ を吸収状態として、各頂点 $v \neq t$ について $E[v] = 1 + \frac{1}{\deg(v)} \sum_{u \in N(v)} E[u]$ を立て、ガウス消去法で解く。

ヒント2: アプローチ

クエリごとに異なる $t$ について連立方程式を解くと $O(Q N^3)$。代わりに全対 Hitting Time を $O(N^4)$ で前処理する。電気抵抗との対応: $H(s, t) + H(t, s) = 2M \cdot R_{eff}(s, t)$。

ヒント3: 誘導

MOD = 10**9 + 7

def gauss(A, b, n):
    """Solve Ax = b over integers mod p"""
    mat = [A[i][:] + [b[i]] for i in range(n)]
    for col in range(n):
        # Find pivot, swap, eliminate
        ...
    return [mat[i][n] for i in range(n)]

# For target t:
# E[t] = 0
# For v != t: deg[v] * E[v] - sum(E[u] for u in adj[v]) = deg[v]

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def gauss_mod(A, b, n, mod):
    mat = [row[:] + [b[i]] for i, row in enumerate(A)]
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if mat[row][col] % mod != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        mat[col], mat[pivot] = mat[pivot], mat[col]
        inv = pow(mat[col][col], mod - 2, mod)
        for row in range(n):
            if row != col and mat[row][col] % mod != 0:
                factor = mat[row][col] * inv % mod
                for k in range(n + 1):
                    mat[row][k] = (mat[row][k] - factor * mat[col][k]) % mod
        for k in range(n + 1):
            mat[col][k] = mat[col][k] * inv % mod
    return [mat[i][n] % mod for i in range(n)]

def solve():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        adj[u].append(v)
        adj[v].append(u)

    deg = [len(adj[v]) for v in range(N)]

    # Precompute hitting times H[s][t] for all s, t
    H = [[0] * N for _ in range(N)]

    for t in range(N):
        other = [v for v in range(N) if v != t]
        idx = {v: i for i, v in enumerate(other)}

        n_var = N - 1
        A = [[0] * n_var for _ in range(n_var)]
        b = [0] * n_var

        for v in other:
            i = idx[v]
            # deg[v] * E[v] - sum_{u in adj[v]} E[u] = deg[v]
            A[i][i] = deg[v]
            b[i] = deg[v]
            for u in adj[v]:
                if u != t:
                    j = idx[u]
                    A[i][j] = (A[i][j] - 1) % MOD

        sol = gauss_mod(A, b, n_var, MOD)

        for i, v in enumerate(other):
            H[v][t] = sol[i] % MOD

    Q = int(input())
    results = []
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1; t -= 1
        results.append(H[s][t])

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

1マルコフ連鎖と Hitting Time の定式化
頂点 $t$ を吸収状態とする。各頂点 $v \neq t$ について: $E[v] = 1 + \frac{1}{\deg(v)} \sum_{u \in N(v)} E[u], \quad E[t] = 0$。これは $N-1$ 元の連立1次方程式。

2ガウス消去法（mod p）
$\mathbb{F}_p$ 上のガウス消去法で解く。$O(N^3)$。各ターゲット $t$ について独立に解くので全体 $O(N^4)$。

3電気抵抗との対応（高度な洞察）
$H(s, t) + H(t, s) = 2M \cdot R_{eff}(s, t)$。実効抵抗は擬似逆行列（ラプラシアン）で全対 $O(N^3)$ に計算可能。

4クエリ処理
前処理でテーブルを構築し、クエリ $O(1)$。

よくあるミス

ミス	原因	正しい書き方
$E[t] = 0$ を連立方程式に含めてしまう	$t$ は吸収状態なので変数から除外	$t$ 以外の $N-1$ 変数のみで立式
`deg[v]` を乗算せずに分数のまま解く	MOD 演算で分数は逆元を使う	両辺に `deg[v]` を掛けて整数化
有向グラフの場合と混同する	無向グラフでは $H(s,t) \neq H(t,s)$ が起きうる	各方向を独立に計算する
連立方程式の行列サイズを $N$ にしてしまう	$t$ を除いて $N-1$	`other = [v for v in range(N) if v != t]`

次のステップ

発展問題: 有向グラフの期待到達時間（推移確率行列のスペクトル解析）
さらに難しい: カバー時間（全頂点を訪問するまでの期待ステップ数）の計算

自己評価

完全理解おおむね理解要復習

Day 022-Q5 — 確率的グラフ問題（ランダムウォークの停止時間・Hitting Time）

問題