概要

この問題は、一直線上に並んだ各地点において、複数の電波塔から届く「受信強度の合計」を効率的に計算し、与えられた耐電磁値 \(T_i\) を超えない範囲でその最大値を求める問題です。

考察

受信強度の性質

地点 \(i\) における電波塔 \(j\)（位置 \(P_j\), 出力 \(B_j\)）の受信強度 \(f_j(i)\) は以下のように定義されます： - \(f_j(i) = \max(0, B_j - |i - P_j|)\)

この式を、受信強度が正（\(f_j(i) > 0\)）となる範囲について分解して考えます。 \(B_j - |i - P_j| > 0\) となるのは、 \(|i - P_j| < B_j\) 、すなわち \(P_j - B_j < i < P_j + B_j\) のときです。 この範囲を \(L = P_j - B_j + 1\) から \(R = P_j + B_j - 1\) とすると、地点 \(i\) における強度は以下の2つの区間に分けられます：

1. 左側（増加区間）: \(i \in [L, P_j]\) のとき \(f_j(i) = B_j - (P_j - i) = i - (P_j - B_j) = i - (L - 1)\) これは、傾きが \(+1\)、切片が \(-(L-1)\) の一次関数です。

2. 右側（減少区間）: \(i \in [P_j + 1, R]\) のとき \(f_j(i) = B_j - (i - P_j) = (P_j + B_j) - i = (R + 1) - i\) これは、傾きが \(-1\)、切片が \(+(R+1)\) の一次関数です。

素朴なアプローチの限界

各地点 \(i\) について、すべての電波塔 \(j\) の受信強度を計算して合計すると、計算量は \(O(N \times M)\) となります。\(N, M \le 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

いもす法の応用

各地点 \(i\) での合計受信強度 \(S_i\) は、その地点をカバーする各電波塔の一次関数の和となります。 \(S_i = \sum (a_j \cdot i + b_j) = i \cdot (\sum a_j) + (\sum b_j)\) ここで、\(a_j\) は傾き（\(+1\) または \(-1\)）、\(b_j\) は切片です。

このように「特定の区間に一次関数を加算する」操作は、いもす法（差分配列）を拡張することで効率的に行えます。 - 傾き \(a_j\) の総和を管理する差分配列 cnt_diff - 切片 \(b_j\) の総和を管理する差分配列 val_diff

これらを用意し、各電波塔の影響範囲の始点と終点で値を更新することで、各地点の \(S_i\) を \(O(1)\) で計算できるようになります。

アルゴリズム

1. 差分配列の準備: 長さ \(N+2\) の配列 cnt_diff と val_diff を \(0\) で初期化します。

2. 電波塔の情報を反映: 各電波塔 \((P_j, B_j)\) について：

   • 増加区間 \([s_1, e_1]\) （ただし \(s_1 = \max(1, P_j - B_j + 1), e_1 = P_j\)）:
     • cnt_diff の \(s_1\) に \(+1\)、\(e_1+1\) に \(-1\) を加算
     • val_diff の \(s_1\) に \(-(L-1)\)、\(e_1+1\) に \(+(L-1)\) を加算
   • 減少区間 \([s_2, e_2]\) （ただし \(s_2 = P_j + 1, e_2 = \min(N, P_j + B_j - 1)\)）:
     • cnt_diff の \(s_2\) に \(-1\)、\(e_2+1\) に \(+1\) を加算
     • val_diff の \(s_2\) に \(+(R+1)\)、\(e_2+1\) に \(-(R+1)\) を加算

3. 合計強度の算出と判定: 地点 \(i = 1\) から \(N\) まで走査しながら：

   • curr_cnt (傾きの累積和) と curr_val (切片の累積和) を更新します。
   • 地点 \(i\) での合計強度 \(S_i = i \cdot \text{curr\_cnt} + \text{curr\_val}\) を計算します。
   • \(S_i \le T_i\) であれば、その地点は正常に動作します。この条件を満たす \(S_i\) の最大値を保持します。

計算量

• 時間計算量: \(O(N + M)\)
  • 各電波塔の処理に \(O(M)\)、各地点の走査に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 耐電磁値の配列 \(T\) と、2つの差分配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 範囲のクリッピング: 電波塔の影響範囲が地点 \(1\) 未満や地点 \(N\) を超える場合があるため、max(1, ...) や min(N, ...) を使って適切に区間を制限する必要があります。

• 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() や sys.stdout.write を利用して入出力を高速化するのが一般的です。

• インデックスの対応: 地点番号は \(1\) から始まりますが、配列のインデックスは \(0\) から始まることが多いため、ズレに注意が必要です。今回のコードでは計算を簡略化するため、差分配列を \(1\) インデックスで扱っています。

  ソースコード

import sys

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # Read N and M
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # Read T values: T[0] corresponds to point 1, T[1] to point 2, ..., T[N-1] to point N
    T = [int(next(it)) for _ in range(N)]
    
    # Use difference arrays to calculate total reception strength S_i at each point i
    # S_i = i * curr_cnt + curr_val, where curr_cnt and curr_val are prefix sums of differences.
    cnt_diff = [0] * (N + 2)
    val_diff = [0] * (N + 2)
    
    for _ in range(M):
        try:
            P = int(next(it))
            B = int(next(it))
        except StopIteration:
            break
        
        # The influence range of a tower at P with power B is (P - B, P + B).
        # Reception strength at point i is f(i) = B - |i - P|.
        L = P - B + 1
        R = P + B - 1
        
        # Part 1: i in [max(1, L), P]
        # In this range, f(i) = B - (P - i) = i - (P - B) = i - (L - 1).
        s1 = L if L > 1 else 1
        e1 = P
        if s1 <= e1:
            cnt_diff[s1] += 1
            cnt_diff[e1 + 1] -= 1
            val_diff[s1] -= (L - 1)
            val_diff[e1 + 1] += (L - 1)
            
        # Part 2: i in [P + 1, min(N, R)]
        # In this range, f(i) = B - (i - P) = (P + B) - i = (R + 1) - i.
        s2 = P + 1
        e2 = R if R < N else N
        if s2 <= e2:
            cnt_diff[s2] -= 1
            cnt_diff[e2 + 1] += 1
            val_diff[s2] += (R + 1)
            val_diff[e2 + 1] -= (R + 1)
    
    max_total_strength = 0
    curr_cnt = 0
    curr_val = 0
    found_working = False
    
    # Iterate through each point i from 1 to N to calculate total reception strength S_i.
    for i in range(1, N + 1):
        curr_cnt += cnt_diff[i]
        curr_val += val_diff[i]
        S_i = i * curr_cnt + curr_val
        
        # Check if the receiver is not overloaded at point i.
        if S_i <= T[i-1]:
            if not found_working or S_i > max_total_strength:
                max_total_strength = S_i
                found_working = True
    
    # Output the maximum total reception strength among working points.
    sys.stdout.write(str(max_total_strength) + '\n')

if __name__ == '__main__':
    solve()

---

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