概要

一列に並んだ建物に対して、複数回の爆発が起こるたびに中心の建物とその隣接建物の耐久値が減る。最終的に耐久値が1以上の建物の数を求める問題。

考察

この問題では、各爆発が建物の耐久値に直接的な影響を与えるため、全ての爆発を順番にシミュレーションする必要があります。

重要な観察点は以下の通りです： - 各爆発では、中心の建物に \(D_j\) のダメージ、左右の隣接建物には \(\lfloor D_j / 2 \rfloor\) のダメージが加わる。 - 耐久値が負になっても問題なく扱う必要がある（倒壊しても影響を受ける）。 - 建物の数 \(N\) や爆発の回数 \(M\) が最大 \(2 \times 10^5\) なので、各爆発ごとに定数時間で処理できるようにする必要がある。

素朴な方法（例えば、毎回範囲 damage を更新するなど）では、処理時間が間に合わない可能性があるため、1回の爆発を最大3箇所（中心＋左右）に対して定数時間で処理することが重要です。

アルゴリズム

1. 各建物の初期耐久値を配列 durability に格納します。
2. 各爆発について以下のように処理します：
   • 中心の建物 \(T_j\) に対して \(D_j\) のダメージを加える。
   • 存在すれば、左隣の建物に対して \(\lfloor D_j / 2 \rfloor\) のダメージを加える。
   • 存在すれば、右隣の建物に対しても同様にダメージを加える。
3. 全ての爆発が終わったら、durability 配列を見ながら耐久値が1以上の建物の数をカウントして出力します。

この方法では、各爆発が高々3つの要素にしか影響を与えないので、効率的です。

例

入力例：

5 2
10 5 8 6 9
3 4
2 6

初期状態：[10, 5, 8, 6, 9]

1回目の爆発（建物3、威力4）： - 建物3: 8 → 4 - 建物2: 5 → 3 - 建物4: 6 → 4

→ [10, 3, 4, 4, 9]

2回目の爆発（建物2、威力6）： - 建物2: 3 → -3 - 建物1: 10 → 7 - 建物3: 4 → 1

→ [7, -3, 1, 4, 9]

最終的に耐久値が1以上なのは：建物1, 3, 4, 5 → 合計4個

計算量

• 時間計算量: \(O(N + M)\)
  （初期化に \(O(N)\)、各爆発処理に \(O(1) \times M\)）
• 空間計算量: \(O(N)\)
  （耐久値を記録する配列）

実装のポイント

• 建物の番号は1-indexedで入力されるので、内部処理では0-indexedに変換する必要がある。
• 左右の隣接チェックを行う際に、端の建物（index 0 または N-1）へのアクセスを誤らないよう注意。
• ダメージは整数除算（//）で行い、小数点以下切り捨てを正確に処理する。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    H = list(map(int, data[2:2+N]))
    
    # 爆発情報をパース
    explosions = []
    for j in range(M):
        T = int(data[2 + N + 2*j]) - 1  # 0-indexedにする
        D = int(data[2 + N + 2*j + 1])
        explosions.append((T, D))
    
    # 各建物の耐久値を管理（初期値）
    durability = H[:]
    
    # 各爆発を処理
    for T, D in explosions:
        # 中心の建物
        durability[T] -= D
        
        # 左隣の建物（存在すれば）
        if T > 0:
            durability[T - 1] -= D // 2
            
        # 右隣の建物（存在すれば）
        if T < N - 1:
            durability[T + 1] -= D // 2
    
    # 耐久値が1以上（倒壊していない）建物の数をカウント
    count = sum(1 for d in durability if d >= 1)
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。