Day 021-Q2 | 確率・期待値DP（マルコフ連鎖の吸収時間）

問題

$N$ 個の状態を持つマルコフ連鎖がある。状態 $0$ が吸収状態（到達したらゲーム終了）で、状態 $i$ ($1 \leq i \leq N-1$) から状態 $j$ へ確率 $p_{ij}$ で遷移する。

初期状態 $S$ から出発したとき、状態 $0$ に到達するまでのステップ数の期待値を求めよ。さらに、$Q$ 個のクエリ $(S_k)$ に答えよ。各クエリで初期状態 $S_k$ からの期待値を出力せよ。

入力形式

N
（N-1 行）: i j p  （状態 i から状態 j へ確率 p/10000 で遷移）
Q
S_1
S_2
...
S_Q

制約

$2 \leq N \leq 500$

各状態 $i$ ($1 \leq i \leq N-1$) からの遷移確率の和は $1$

状態 $0$ は必ず有限期待値で到達可能（到達不能な状態は期待値 $\infty$）

$1 \leq Q \leq 10^5$

入出力例

入力例 1

出力例 1

10/3

分数で出力。既約分数かつ $\infty$ の場合は -1

ヒント (段階的開示)

ヒント1: 方向性

$E[i]$ = 状態 $i$ から吸収状態 $0$ に到達するまでの期待ステップ数とおく。全非吸収状態について連立方程式を立てる。

ヒント2: アプローチ

$E[i] = 1 + \sum_j p_{ij} E[j]$（$j=0$ の項は $E[0]=0$）。これは $(I - P) E = \mathbf{1}$ の形の線形方程式系。$P$ を非吸収状態間の遷移行列とする。

ヒント3: 誘導

from fractions import Fraction
import numpy as np  # 大きなケースはfloatで近似

# N=500 → ガウス消去法 O(N^3) = 1.25×10^8 → Python では遅い
# → 分数ではなく float で解く（誤差許容）
# → あるいはmod p で解く（答えが有理数のため）

# mod p で解く場合：
MOD = 998244353
def modinv(a, m=MOD):
    return pow(a, m-2, m)

模範解答 (Python)

import sys
from collections import defaultdict

def solve():
    data = sys.stdin.read().split()
    pos = 0

    N = int(data[pos]); pos += 1
    MOD = 998244353

    trans = defaultdict(list)
    edges = []
    while pos + 2 < len(data):
        try:
            i, j, p = int(data[pos]), int(data[pos+1]), int(data[pos+2])
            if i == 0:
                break
            edges.append((i, j, p))
            pos += 3
        except:
            break

    n = N - 1  # 非吸収状態の数

    inv10000 = pow(10000, MOD-2, MOD)

    A = [[0] * n for _ in range(n)]
    b = [1] * n  # 右辺はすべて 1

    for i in range(1, N):
        A[i-1][i-1] = 1  # 対角成分 = 1

    for (i, j, p) in edges:
        if j == 0:
            continue  # E[0] = 0 なので寄与なし
        A[i-1][j-1] = (A[i-1][j-1] - p * inv10000) % MOD

    # ガウス消去法 mod p
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if A[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        A[col], A[pivot] = A[pivot], A[col]
        b[col], b[pivot] = b[pivot], b[col]

        inv_diag = pow(A[col][col], MOD-2, MOD)
        for j in range(n):
            A[col][j] = A[col][j] * inv_diag % MOD
        b[col] = b[col] * inv_diag % MOD

        for row in range(n):
            if row == col or A[row][col] == 0:
                continue
            factor = A[row][col]
            for j in range(n):
                A[row][j] = (A[row][j] - factor * A[col][j]) % MOD
            b[row] = (b[row] - factor * b[col]) % MOD

    E = b

    Q = int(data[pos]); pos += 1
    results = []
    for _ in range(Q):
        s = int(data[pos]); pos += 1
        if s == 0:
            results.append(0)
        else:
            results.append(E[s-1])

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

solve()

Step-by-Step 解説

1期待値方程式の立式
$E[i]$ を状態 $i$ から吸収状態まで到達するステップ数の期待値とすると $E[i] = 1 + \sum_{j=1}^{N-1} p_{ij} E[j] \quad (E[0] = 0)$。移項すると $E[i] - \sum_{j=1}^{N-1} p_{ij} E[j] = 1$。行列形式: $(I - P) \mathbf{E} = \mathbf{1}$。

2mod p でのガウス消去法
答えが有理数なので $\text{mod } p$ で解ける。$O(N^3)$ のガウス消去法を使う。$N \leq 500$ なら $500^3 / 10^8 \approx 1.25$ 秒（PyPy では通るが Python は厳しい）。

3到達不能状態の処理
$(I-P)$ が特異（ピボットが $0$）の場合、その状態からは吸収状態に到達不能。期待値は $\infty$ → -1 を出力する。

4クエリへの答え方
$\mathbf{E}$ を一度計算すれば全クエリに $O(1)$ で答えられる。

よくあるミス

ミス	原因	正しい書き方
$E[0]$ を変数として含める	不要、$E[0]=0$ は定数	非吸収状態のみ $(N-1) \times (N-1)$ 系
遷移確率の分母を間違える	$p/10000$ のつもりが $p$ のまま	`inv10000 = pow(10000, MOD-2, MOD)` を掛ける
到達不能チェックを省く	ピボットが0のときにゼロ除算	ピボット0なら期待値$\infty$ とする

Day 021-Q2 — 確率・期待値DP（マルコフ連鎖の吸収時間）

問題