概要

各マスの石ブロックが崩壊するステップ番号を求める問題です。これは「グリッドの外側」を始点とし、各マスを通過するときに耐久値 \(C_{i,j}\) をコストとして加算する最短経路問題（Dijkstra法）に帰着できます。

考察

崩壊時刻の漸化式

あるマス \(u\) が崩壊するステップ番号を \(t(u)\) とします。崩壊の仕組みを丁寧に追うと、次の関係が見えてきます。

• 境界マス（1行目・\(H\)行目・1列目・\(W\)列目）の場合：初期状態からグリッド外側に接して風雨にさらされているので、ステップ \(1\) から毎ステップ耐久値が \(1\) ずつ減り続けます。よって \(C_u\) ステップ後にちょうど \(0\) になり崩壊します。すなわち $\(t(u) = C_u\)$

• 内部マスの場合：このマスは、隣接する \(4\) マスのいずれかが崩壊して空きマスになった瞬間に「風雨にさらされる」状態になります。問題のルールより、新たにさらされたマスの耐久値の減少は 次のステップから 始まります。隣接マス \(v\) が時刻 \(t(v)\) に崩壊したとすると、\(u\) はステップ \(t(v)+1\) から減り始め、\(C_u\) ステップ後に崩壊します。最も早く崩壊する隣接マスによって \(u\) がさらされるので、 $\(t(u) = \min_{v \in \text{隣接}} t(v) + C_u\)$

このとき「同一ステップ内で連鎖崩壊は起きない（次のステップから減少が始まる）」というルールが、ちょうど隣接マスの崩壊時刻にそのまま \(C_u\) を足す形に対応します。

統一的な見方

グリッドの外側を「時刻 \(0\) に崩壊した仮想的なマス」とみなすと、境界マスの式 \(t(u) = C_u\) も「\(t(\text{外側})=0\) に \(C_u\) を足したもの」として、内部マスと同じ漸化式に統一できます。

結局、\(t(u)\) は

グリッドの外側から \(u\) まで、通ったマスの耐久値 \(C\) の総和が最小になる経路のコスト

に一致します。これは最短経路問題そのものです。

素朴な方法ではなぜダメか

耐久値は最大 \(10^9\) で、崩壊までのステップ数も非常に大きくなり得ます。ステップを \(1\) つずつ進めるシミュレーションは到底間に合いません。上記の最短経路への言い換えにより、ステップ数に依存しない効率的な計算が可能になります。

アルゴリズム

各マスを頂点とし、隣接マス \(v \to u\) に「\(u\) に入るときコスト \(C_u\) がかかる辺」を張ったグラフ上で Dijkstra法 を行います。

1. すべての境界マス \(u\) について、初期距離 \(\text{dist}[u] = C_u\) として優先度付きキューに入れる（外側からコスト \(C_u\) で到達する状態）。
2. 通常のDijkstra法でキューから最小コストの頂点 \(u\) を取り出し、隣接マス \(v\) へ \(\text{dist}[v] = \text{dist}[u] + C_v\) で緩和していく。
3. 計算した \(\text{dist}[u]\) が、そのマスの崩壊ステップ番号 \(t(u)\) になる。

クエリは前計算した \(\text{dist}\) 配列を参照するだけで \(O(1)\) で答えられます。

計算量

頂点数を \(N = H \times W\) とします。各頂点は最大 \(4\) 本の辺を持つため辺数は \(O(N)\) です。

• 時間計算量: \(O(N \log N + Q)\)
• 空間計算量: \(O(N)\)

\(N \le 500 \times 500 = 250000\)、\(Q \le 10^5\) なので十分高速に動作します。

実装のポイント

• 2次元座標の1次元化：マス \((i, j)\) を i*W + j という1次元のインデックスに変換して扱うと、配列アクセスやヒープ操作が高速かつ簡潔になります。逆変換は divmod(u, W) で行えます。

• 境界判定：i == 0 or i == H-1 or j == 0 or j == W-1 のとき境界マスです。これらを初期状態でヒープに入れます。

• Dijkstraの遅延削除：ヒープから取り出した距離 d が現在の dist[u] より大きい場合（d > dist[u]）は、すでに更新済みの古い情報なのでスキップします。これにより計算量が保たれます。

• 隣接マスへ移動する際は、グリッドの範囲外に出ないよう i > 0, i < H-1, j > 0, j < W-1 の条件で上下左右を判定します。

  ソースコード

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(data[idx]); idx += 1
    W = int(data[idx]); idx += 1
    N = H * W
    C = [0]*N
    for i in range(N):
        C[i] = int(data[idx]); idx += 1
    INF = float('inf')
    dist = [INF]*N
    heap = []
    push = heapq.heappush
    pop = heapq.heappop
    # 境界マスを初期化
    for i in range(H):
        base = i*W
        on_row_edge = (i == 0 or i == H-1)
        for j in range(W):
            if on_row_edge or j == 0 or j == W-1:
                p = base + j
                c = C[p]
                dist[p] = c
                push(heap, (c, p))
    while heap:
        d, u = pop(heap)
        if d > dist[u]:
            continue
        i, j = divmod(u, W)
        if i > 0:
            v = u - W; nd = d + C[v]
            if nd < dist[v]:
                dist[v] = nd; push(heap, (nd, v))
        if i < H-1:
            v = u + W; nd = d + C[v]
            if nd < dist[v]:
                dist[v] = nd; push(heap, (nd, v))
        if j > 0:
            v = u - 1; nd = d + C[v]
            if nd < dist[v]:
                dist[v] = nd; push(heap, (nd, v))
        if j < W-1:
            v = u + 1; nd = d + C[v]
            if nd < dist[v]:
                dist[v] = nd; push(heap, (nd, v))
    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        r = int(data[idx]); k = int(data[idx+1]); idx += 2
        out.append(dist[(r-1)*W + (k-1)])
    sys.stdout.write('\n'.join(map(str, out)))
    sys.stdout.write('\n')

main()

---

この解説は claude4.8opus-high によって生成されました。