概要

\(N\) 個の地点それぞれについて、\(M\) 基の電波塔からの正の受信強度の合計を効率的に求め、耐電磁値以下である地点の中から合計の最大値を求める問題です。

考察

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

各地点 \(i\) について全電波塔 \(j\) の受信強度 \(B_j - |i - P_j|\) を計算すると、\(O(NM)\) の計算量になります。\(N, M\) が最大 \(2 \times 10^5\) なので、最大 \(4 \times 10^{10}\) 回の計算となり、到底間に合いません。

重要な気づき：テント関数の構造

電波塔 \(j\)（位置 \(P_j\)、出力 \(B_j\)）が地点 \(i\) に与える受信強度は \(B_j - |i - P_j|\) ですが、これが正になる範囲は \(P_j - B_j + 1 \leq i \leq P_j + B_j - 1\) です。この範囲外では寄与は \(0\) です。

この関数はいわゆるテント関数（三角形の形）で、中心 \(P_j\) でピーク \(B_j\) を取り、左右に傾き \(\pm 1\) で減少します。具体的には：

• 左側（\(i \leq P_j\)）：寄与 \(= (B_j - P_j) + i\)（\(i\) に対して傾き \(+1\) の一次関数）
• 右側（\(i > P_j\)）：寄与 \(= (B_j + P_j) - i\)（\(i\) に対して傾き \(-1\) の一次関数）

一次関数の区間加算をまとめる

全電波塔の寄与の合計 \(S(i)\) は、複数の一次関数の和です。一次関数 \(f(i) = a + b \cdot i\) の区間加算は、定数項 \(a\) の累積和と \(i\) の係数 \(b\) の累積和を別々に管理する「いもす法（差分配列）」で \(O(1)\) ずつ処理できます。

アルゴリズム

1. 差分配列の準備：diff_const（定数項用）と diff_coeff（\(i\) の係数用）の2本を用意する。

2. 各電波塔について差分配列を更新：

   • 有効範囲 \(L = \max(1, P_j - B_j + 1)\)、\(R = \min(N, P_j + B_j - 1)\) を計算。
   • 左側 \([L, P_j]\)：定数項 \((B_j - P_j)\) と係数 \(+1\) を区間加算。
   • 右側 \([P_j+1, R]\)：定数項 \((B_j + P_j)\) と係数 \(-1\) を区間加算。

3. 累積和を取って各地点の受信強度合計を復元：

   • 地点 \(i\) での合計は \(S(i) = \text{cur\_const} + \text{cur\_coeff} \times i\)。

4. 答えの計算：\(S(i) \leq T_i\) を満たす地点の中で \(S(i)\) の最大値を出力。

具体例

電波塔が位置 \(3\)、出力 \(3\) の場合、有効範囲は \([1, 5]\) で寄与は：

地点 \(i\)	1	2	3	4	5
寄与	1	2	3	2	1

左側 \([1,3]\)：\((3-3) + i = i\)、右側 \([4,5]\)：\((3+3) - i = 6 - i\)。確かに一致します。

計算量

• 時間計算量: \(O(N + M)\)（差分配列の更新に \(O(M)\)、累積和の復元と答えの探索に \(O(N)\)）
• 空間計算量: \(O(N + M)\)（差分配列・耐電磁値配列・電波塔情報の格納）

実装のポイント

• 差分配列の添字は \(N+2\) まで確保しておくと、\(R+1\) が \(N+1\) になっても範囲外アクセスを防げます。

• 左側と右側の範囲が空にならないかの条件分岐（\(L \leq P\) や \(P+1 \leq R\)）を忘れないこと。

• \(T_i\) が最大 \(10^{14}\) と大きいため、64ビット整数が必要ですが、Python では整数のオーバーフローを気にする必要はありません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        T[i] = int(input_data[idx]); idx += 1
    
    towers = []
    for j in range(M):
        P = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        towers.append((P, B))
    
    # For each tower at position P with power B, it contributes B - |i - P| to point i,
    # but only when B - |i - P| > 0, i.e., when P - B + 1 <= i <= P + B - 1.
    # 
    # The contribution is a tent function centered at P with peak B.
    # For i <= P: contribution = B - (P - i) = (B - P) + i
    # For i >= P: contribution = B - (i - P) = (B + P) - i
    #
    # We can compute the sum of all contributions using a difference array approach.
    # Each tent function on [L, R] with peak at P can be decomposed into:
    #   - Left part [L, P]: adds a linear function with slope +1 and intercept (B - P)
    #   - Right part [P+1, R]: adds a linear function with slope -1 and intercept (B + P)
    #
    # To handle sums of linear functions efficiently, we use the trick:
    # sum of (a + b*i) over multiple functions = (sum of a's) + (sum of b's) * i
    # We maintain two difference arrays: one for the constant part and one for the coefficient of i.
    
    # For slope +1 part (left side): f(i) = (B-P) + 1*i, range [L, P]
    # For slope -1 part (right side): f(i) = (B+P) + (-1)*i, range [P+1 if P<R else skip, R]
    # But we also need to handle the "only positive" constraint - which is already handled by L,R bounds.
    
    # We'll use prefix sum approach for piecewise linear functions.
    # diff_const and diff_coeff arrays of size N+2
    
    diff_const = [0] * (N + 2)
    diff_coeff = [0] * (N + 2)
    
    for P, B in towers:
        L = max(1, P - B + 1)
        R = min(N, P + B - 1)
        
        # Left part: [L, P], contribution = (B - P) + i
        if L <= P:
            lp = L
            rp = min(P, R)
            # Add constant (B - P) on [lp, rp]
            diff_const[lp] += (B - P)
            diff_const[rp + 1] -= (B - P)
            # Add coefficient +1 on [lp, rp]
            diff_coeff[lp] += 1
            diff_coeff[rp + 1] -= 1
        
        # Right part: [P+1, R], contribution = (B + P) - i
        if P + 1 <= R:
            lp = P + 1
            rp = R
            # Add constant (B + P) on [lp, rp]
            diff_const[lp] += (B + P)
            diff_const[rp + 1] -= (B + P)
            # Add coefficient -1 on [lp, rp]
            diff_coeff[lp] += -1
            diff_coeff[rp + 1] -= -1
    
    # Now compute prefix sums to get actual const and coeff at each point
    cur_const = 0
    cur_coeff = 0
    
    ans = -1
    
    for i in range(1, N + 1):
        cur_const += diff_const[i]
        cur_coeff += diff_coeff[i]
        
        total = cur_const + cur_coeff * i
        
        if total <= T[i]:
            if total > ans:
                ans = total
    
    print(ans)

main()

---

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