概要

グリッドの外側から風雨による侵食が進行し、各マスの石ブロックが崩壊するステップ数を求める問題です。 この問題は、グリッドをグラフとみなすことで、外周から各マスへの「重み付き最短経路問題」に帰着させ、ダイクストラ法を用いて高速に解くことができます。

考察

ルールの整理

• 各ステップで、風雨にさらされているマスの耐久値が \(1\) 減少します。
• 耐久値が \(0\) になるとそのマスは崩壊し、空きマスになります。
• 空きマスに隣接するマスは、次のステップから風雨にさらされます（耐久値が減少し始めます）。

具体的な挙動の観察

例として、外周にあるマス \(A\)（耐久値 \(C_A\)）と、その内側に隣接するマス \(B\)（耐久値 \(C_B\)）の関係を考えてみましょう。

1. マス \(A\) は最初から風雨にさらされています。したがって、ステップ \(1\) から耐久値が減少し始め、ステップ \(C_A\) の終了時に崩壊します。
2. マス \(B\) は、マス \(A\) が崩壊した次のステップ、すなわちステップ \(C_A + 1\) から風雨にさらされ始めます。
3. マス \(B\) が風雨にさらされ始めてから崩壊するまでには \(C_B\) ステップかかります。したがって、マス \(B\) が崩壊するのはステップ \((C_A + 1) + C_B - 1 = C_A + C_B\) となります。

一般化すると、あるマス \(v\) が崩壊するステップ数は、隣接するマス \(u\) が崩壊したステップ数 \(dist[u]\) を用いて、以下のように表せます。 $\(dist[v] = dist[u] + C_v\)$

マス \(v\) は上下左右の \(4\) 方向から侵食される可能性があるため、最も早く侵食が到達するルートが採用されます。すなわち： $\(dist[v] = \min_{u \in \text{adj}(v)} (dist[u]) + C_v\)\( となります（ただし、外周のマスは初期状態で \)dist[\text{外周}] = C_{\text{外周}}$ です）。

素朴なシミュレーションの限界

ステップごとにグリッドの状態を更新する素朴なシミュレーションを考えると、各マスの耐久値 \(C_{i,j}\) は最大で \(10^9\) であるため、シミュレーションのステップ数が膨大になり、実行時間制限（TLE）に間に合いません。 そこで、上記のように「崩壊するステップ数」の関係式に注目し、シミュレーションを行わずに直接崩壊ステップを求めるアプローチが必要になります。

アルゴリズム

この問題は、グリッドの各マスを頂点、隣接するマス同士を辺で結んだグラフにおける最短経路問題として解くことができます。

1. グラフの構築: 各マスを頂点 \(u\) とします。隣接する \(4\) 方向のマスとの間に無向辺を張ります。

2. ダイクストラ法の適用:

   • 各頂点 \(u\) への「崩壊ステップ数」を保持する配列 dist を無限大（\(\infty\)）で初期化します。
   • 初期状態として、外周にあるマス（\(1\) 行目、\(H\) 行目、\(1\) 列目、\(W\) 列目）の dist をそのマスの耐久値 \(C_{i,j}\) で更新し、優先度付きキュー（ヒープ）に追加します。
   • 優先度付きキューから最も崩壊ステップ数が小さい頂点 \(u\)（確定値 \(d = dist[u]\)）を取り出します。
   • \(u\) に隣接する各頂点 \(v\) について、新しく計算した崩壊ステップ数 \(nd = d + C_v\) が現在の \(dist[v]\) より小さければ、\(dist[v]\) を \(nd\) で更新し、キューに \((nd, v)\) を追加します。

3. クエリの処理: ダイクストラ法によりすべてのマスの崩壊ステップ数 dist が求まったら、各クエリ \((R_k, K_k)\) に対して dist の値を \(O(1)\) で出力します。

計算量

• 時間計算量: \(O(HW \log(HW) + Q)\)
  • 頂点数 \(V = HW\)、辺の数 \(E \approx 4HW\) です。
  • ダイクストラ法の計算量は \(O(E \log V)\) となるため、全体で \(O(HW \log(HW))\) となります。
  • クエリの処理は \(Q\) 個のクエリに対してそれぞれ \(O(1)\) で答えられるため、全体で \(O(HW \log(HW) + Q)\) となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(HW)\)
  • グラフの隣接リスト、dist 配列、および優先度付きキューを保持するために \(O(HW)\) のメモリを使用します。

実装のポイント

• 1次元配列での管理: 2次元のグリッド座標 \((r, c)\) を \(r \times W + c\) という式を用いて1次元のインデックスに変換して管理することで、実装をシンプルにし、メモリ効率や実行速度を向上させています。

• 高速な入出力: Pythonでは入力数・出力数が多い（\(Q \le 10^5\)）ため、sys.stdin.read().split() を用いて入力を一括で読み込み、出力も \n.join() で一括で出力することで、入出力のボトルネックを回避しています。

  ソースコード

import heapq
import sys


def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    H = int(input_data[0])
    W = int(input_data[1])

    # C を1次元配列として取得
    C_flat = [int(x) for x in input_data[2 : 2 + H * W]]

    # 隣接リストの作成
    adj = [[] for _ in range(H * W)]
    for u in range(H * W):
        r = u // W
        c = u % W
        if r > 0:
            adj[u].append(u - W)
        if r < H - 1:
            adj[u].append(u + W)
        if c > 0:
            adj[u].append(u - 1)
        if c < W - 1:
            adj[u].append(u + 1)

    # ダイクストラ法の初期化
    dist = [float("inf")] * (H * W)
    pq = []

    for u in range(H * W):
        r = u // W
        c = u % W
        if r == 0 or r == H - 1 or c == 0 or c == W - 1:
            dist[u] = C_flat[u]
            pq.append((C_flat[u], u))

    heapq.heapify(pq)

    # ダイクストラ法
    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v in adj[u]:
            nd = d + C_flat[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    # クエリの処理
    q_start = 2 + H * W
    Q = int(input_data[q_start])
    q_start += 1

    out = []
    for k in range(Q):
        r = int(input_data[q_start + 2 * k]) - 1
        c = int(input_data[q_start + 2 * k + 1]) - 1
        out.append(str(dist[r * W + c]))

    print("\n".join(out))


if __name__ == "__main__":
    main()

---

この解説は gemini-3.5-flash-high によって生成されました。