概要

\(N\) 個の建物に対し、指定された地点とその両隣にダメージを与える爆発が \(M\) 回発生します。すべての爆発が終わった後、初期の耐久値を上回るダメージを受けずに生き残った建物の数を求める問題です。

考察

1. 爆発の影響範囲に着目する

一見すると複雑なシミュレーションが必要に思えますが、1回の爆発が影響を与える範囲は非常に限定的です。建物 \(T_j\) で爆発が起きたとき、ダメージを受けるのは以下の最大3つの建物だけです。

• 建物 \(T_j\)（中心）：ダメージ \(D_j\)
• 建物 \(T_j - 1\)（左隣）：ダメージ \(\lfloor D_j / 2 \rfloor\)
• 建物 \(T_j + 1\)（右隣）：ダメージ \(\lfloor D_j / 2 \rfloor\)

2. ダメージの累積

爆発によって建物が倒壊しても、その残骸は残り続け、以降の衝撃波を遮ることはありません。つまり、各建物が受ける最終的な合計ダメージは、「その建物で起きた爆発によるダメージ」と「両隣で起きた爆発による衝撃波のダメージ」を単純に合計したものになります。

爆発の順番を気にする必要はなく、すべての爆発が終わった時点での各建物の合計ダメージを計算すればよいことになります。

3. 計算量の見積もり

もし、1回の爆発ですべての建物（\(N\) 個）を更新していたら、全体の計算量は \(O(N \times M)\) となり、今回の制約（\(N, M \le 2 \times 10^5\)）では実行時間制限に間に合いません。 しかし、今回の問題では1回の爆発につき高々3箇所の値を更新するだけで済むため、爆発の処理は \(O(M)\) で完了します。最後に各建物の生存判定を行う \(O(N)\) と合わせても、十分に間に合わせることができます。

アルゴリズム

1. 長さ \(N\) の配列 damage を用意し、すべて \(0\) で初期化します。
2. \(M\) 回の爆発情報を順に処理します。各爆発 \((T_j, D_j)\) について：
   • damage[T_j] に \(D_j\) を加算する。
   • damage[T_j - 1] に \(\lfloor D_j / 2 \rfloor\) を加算する（左隣が存在する場合）。
   • damage[T_j + 1] に \(\lfloor D_j / 2 \rfloor\) を加算する（右隣が存在する場合）。
3. すべての処理が終わった後、各建物 \(i = 1, \ldots, N\) について、初期耐久値 \(H_i\) と damage[i] を比較します。
4. \(H_i > damage[i]\)（耐久値が \(1\) 以上残っている）を満たす建物の数をカウントして出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、爆発の処理に \(O(M)\)、最後の集計に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 耐久値を保存する配列と、累積ダメージを保存する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 0-indexed への変換: 問題文では建物番号が \(1\) から \(N\) ですが、プログラムの配列では \(0\) から \(N-1\) として扱うと管理しやすくなります。その際、隣接する建物のインデックスが範囲外（\(-1\) や \(N\)）にならないよう条件分岐でチェックする必要があります。

• 高速な入出力: \(N\) と \(M\) が大きいため、Python の input() を繰り返すと時間がかかる場合があります。sys.stdin.read().split() などを使って一括で読み込むのが効率的です。

• 整数の切り捨て除算: Python では // 演算子を使うことで、問題文にある「\(\lfloor D_j / 2 \rfloor\)（床関数）」を簡単に計算できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # 建物の数 N と爆発の回数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各建物の初期耐久値 H_i を取得
    # H は 0-indexed で管理する (建物 1 は H[0])
    H = list(map(int, input_data[2:2+N]))
    
    # 各建物が受ける累積ダメージを格納する配列
    damage = [0] * N
    
    # 爆発情報を順番に処理
    # 爆発の情報は input_data の N+2 番目の要素から始まる
    ptr = 2 + N
    for _ in range(M):
        t_j = int(input_data[ptr])
        d_j = int(input_data[ptr+1])
        ptr += 2
        
        # 建物番号を 0-indexed のインデックスに変換
        idx = t_j - 1
        
        # 爆発の中心となる建物へのダメージ
        damage[idx] += d_j
        
        # 衝撃波による隣接する建物へのダメージ (floor(D_j / 2))
        shock_damage = d_j // 2
        if shock_damage > 0:
            # 左隣の建物が存在する場合
            if idx > 0:
                damage[idx - 1] += shock_damage
            # 右隣の建物が存在する場合
            if idx < N - 1:
                damage[idx + 1] += shock_damage
        
    # すべての爆発が終わった後、生き残っている建物をカウント
    # 耐久値 H[i] から累積ダメージ damage[i] を引いた値が 1 以上であれば倒壊していない
    surviving_count = 0
    for i in range(N):
        if H[i] > damage[i]:
            surviving_count += 1
            
    # 結果を出力
    sys.stdout.write(str(surviving_count) + '\n')

if __name__ == '__main__':
    solve()

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