概要

\(N\) 個の建物に対して \(M\) 回の爆発が発生し、各爆発は中心の建物とその左右隣接建物にダメージを与えます。すべての爆発後に耐久値が \(1\) 以上残っている建物の数を求める問題です。

考察

重要な気づき

この問題で最も重要な観察は、各建物が最終的に受ける総ダメージさえ分かれば良いということです。

爆発の順番に関わらず、各建物への累積ダメージは同じになります。例えば： - 建物 \(i\) は、自身が爆発の中心になった時に威力 \(D\) のダメージを受ける - 建物 \(i\) は、隣接する建物 \(i-1\) または \(i+1\) が中心の時に威力 \(\lfloor D/2 \rfloor\) のダメージを受ける

素朴なアプローチの問題点

各爆発ごとに最大3つの建物を更新するので、\(M\) 回の爆発で \(O(M)\) の計算で済みます。実はこの問題は素朴なアプローチでも十分高速です。

ただし、もし「衝撃波が無限に広がる（距離に応じて減衰）」ような設定だった場合、各爆発で \(O(N)\) 建物を更新する必要があり、全体で \(O(NM)\) となりTLEになる可能性があります。

解法のポイント

各建物が受けるダメージを配列で管理し、すべての爆発を処理した後に、各建物の残り耐久値を計算します。

アルゴリズム

1. ダメージ配列の初期化: 長さ \(N\) の配列 damage を \(0\) で初期化
2. 各爆発の処理: \(M\) 回の爆発それぞれについて
   • 中心の建物 \(T_j\) に威力 \(D_j\) を加算
   • 左隣 \(T_j - 1\) が存在すれば \(\lfloor D_j / 2 \rfloor\) を加算
   • 右隣 \(T_j + 1\) が存在すれば \(\lfloor D_j / 2 \rfloor\) を加算
3. 生存建物のカウント: 各建物 \(i\) について \(H_i - \text{damage}[i] \geq 1\) なら生存

具体例

\(N = 3\), \(H = [10, 5, 8]\) で、爆発が建物2を中心に威力6で起きた場合： - 建物1（左隣）: ダメージ \(\lfloor 6/2 \rfloor = 3\) - 建物2（中心）: ダメージ \(6\) - 建物3（右隣）: ダメージ \(\lfloor 6/2 \rfloor = 3\)

最終耐久値: \([10-3, 5-6, 8-3] = [7, -1, 5]\)

建物2は倒壊（耐久値 \(\leq 0\)）、生存は2棟。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)
  • 各爆発の処理に \(O(1)\)（定数個の建物のみ更新）× \(M\) 回 = \(O(M)\)
  • 生存カウントに \(O(N)\)
• 空間計算量: \(O(N)\)
  • ダメージ配列と耐久値配列の格納に \(O(N)\)

実装のポイント

• 0-indexed への変換: 問題文では建物番号が \(1\) から始まるが、配列は \(0\) から始まるため、入力を読んだ後に T -= 1 で調整

• 境界チェック: 左端（\(T = 0\)）や右端（\(T = N-1\)）の建物が中心の場合、存在しない隣接建物にアクセスしないよう条件分岐が必要

• 整数の切り捨て除算: Python では // 演算子で \(\lfloor D/2 \rfloor\) を計算

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    
    # 各建物へのダメージを累積
    damage = [0] * N
    
    for _ in range(M):
        T, D = map(int, input().split())
        T -= 1  # 0-indexed
        
        # 中心の建物
        damage[T] += D
        
        # 左隣の建物（存在する場合）
        if T > 0:
            damage[T - 1] += D // 2
        
        # 右隣の建物（存在する場合）
        if T < N - 1:
            damage[T + 1] += D // 2
    
    # 倒壊していない建物をカウント
    count = 0
    for i in range(N):
        if H[i] - damage[i] >= 1:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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