概要

道路上の \(N\) 基の電波塔がそれぞれカバー範囲を持ち、整数座標の地点を1つ選んで、その地点をカバーする全塔の信号強度の合計を最大化する問題です。イベントソート（座標圧縮＋スイープライン） を用いて効率的に解きます。

考察

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

各塔のカバー範囲は \([X_i - L_i,\; X_i + R_i]\) であり、座標は最大で \(0 - 10^9 = -10^9\) から \(10^9 + 10^9 = 2 \times 10^9\) まで広がり得ます。すべての整数座標を試すと最大 \(2 \times 10^9\) 回の計算が必要で、明らかに間に合いません。

重要な気づき

信号強度の合計は、カバー範囲の開始・終了が起こる座標でしか変化しません。つまり、隣り合うイベント座標の間では強度の合計は一定です。そこで、カバー範囲の「開始」と「終了」をイベントとして記録し、イベント座標だけを走査すれば十分です。これが スイープライン法 です。

イベントの定義

塔 \(i\) のカバー範囲は整数座標 \([X_i - L_i,\; X_i + R_i]\) です。

• 開始イベント: 座標 \(X_i - L_i\) で \(+C_i\)（カバーが始まる）
• 終了イベント: 座標 \(X_i + R_i + 1\) で \(-C_i\)（カバーが終わる）

終了イベントの座標を \(X_i + R_i + 1\) とするのは、\(X_i + R_i\) の地点までカバーされるため、その 次の座標 で取り消す必要があるからです。

同一座標でのイベント順序

同じ座標に開始と終了のイベントが同時に存在する場合、終了（\(-1\)）を先に処理 します。終了イベント座標 \(r+1\) は「\(r+1\) 以降はカバーしない」ことを意味し、同じ座標で始まる新たなカバーとは独立だからです。ソートキー \((座標, 種類)\) で種類を \(-1, +1\) とすれば、\(-1 < 1\) なので自然に終了が先になります。

アルゴリズム

1. 各塔 \(i\) について、開始イベント \((X_i - L_i, +1, C_i)\) と終了イベント \((X_i + R_i + 1, -1, C_i)\) を生成する。
2. 全イベントを \((座標, 種類)\) の昇順でソートする。
3. 現在の信号強度合計 current_sum を \(0\) で初期化し、イベントを順に処理する：
   • 開始イベントなら current_sum += C_i
   • 終了イベントなら current_sum -= C_i
   • 各イベント処理後に max_sum を更新する。
4. max_sum を出力する。

具体例

塔A: 座標 \(3\), \(L=2\), \(R=1\), \(C=5\) → カバー \([1, 4]\) 塔B: 座標 \(5\), \(L=1\), \(R=2\), \(C=3\) → カバー \([4, 7]\)

イベント: \((1, +1, 5),\; (4, +1, 3),\; (5, -1, 5),\; (8, -1, 3)\)

• 座標 \(1\): \(+5\) → 合計 \(5\)
• 座標 \(4\): \(+3\) → 合計 \(8\) ← 最大！（座標 \(4\) は両方のカバー範囲に含まれる）
• 座標 \(5\): \(-5\) → 合計 \(3\)
• 座標 \(8\): \(-3\) → 合計 \(0\)

答えは \(8\) です。

計算量

• 時間計算量: \(O(N \log N)\)（イベントのソートが支配的）
• 空間計算量: \(O(N)\)（イベントリストの格納）

実装のポイント

• カバー範囲が整数座標上の閉区間 \([X_i - L_i,\; X_i + R_i]\) であるため、終了イベントは \(X_i + R_i + 1\) に置く（半開区間 \([l, r+1)\) に変換するテクニック）。

• 同一座標では終了イベントを先に処理するため、イベントの種類を \(-1\)（終了）と \(+1\)（開始）として座標と合わせてソートすると、自然に正しい順序になる。

• \(N = 0\) の場合でも初期値 \(0\) がそのまま答えになるため、特別な処理は不要。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    events = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        left = X - L
        right = X + R
        events.append((left, 1, C))      # start of coverage
        events.append((right + 1, -1, C)) # end of coverage (right+1 because inclusive)
    
    # Sort events by coordinate, then by type (starts before ends at same coordinate)
    events.sort(key=lambda e: (e[0], e[1]))
    
    # Sweep through events
    current_sum = 0
    max_sum = 0
    
    for coord, typ, c in events:
        if typ == 1:
            current_sum += c
        else:
            current_sum -= c
        if current_sum > max_sum:
            max_sum = current_sum
    
    # Wait, we need to be more careful. Events at the same coordinate should be processed together,
    # and we should check the sum after processing all events at each coordinate.
    # Also, we need to process adds before removes at the same coordinate to get the max.
    
    # Let me redo this properly with grouping by coordinate.
    
    # Actually, let me reconsider. At coordinate `left`, coverage starts (add C).
    # At coordinate `right+1`, coverage ends (subtract C).
    # Between consecutive event coordinates, the sum is constant.
    # We want the maximum sum at any point.
    # After processing all events at a coordinate, the current_sum is valid for [this_coord, next_coord).
    # But we also want to check the sum AT this coordinate after adds but before removes?
    # No - at coordinate `left`, we add. At coordinate `right+1`, we remove.
    # So at coordinate `right`, the coverage is still active. At `right+1` it's removed.
    # So processing: at each coordinate, process all +1 events first, then -1 events.
    # After processing +1 events and before -1 events, that's the sum "at this coordinate" if
    # this coordinate is a left endpoint. But actually we want: after all events at coordinate c,
    # the sum is valid for points in [c, next_event_coord - 1].
    # Hmm, but if at the same coordinate we have both adds and removes, the order matters.
    # At coordinate c: if something starts at c (add) and something ends at c (i.e., right+1 = c, remove),
    # the remove means coverage ended at c-1. The add means coverage starts at c.
    # So at point c, the add is active and the remove has happened. So we should process removes first? No.
    # Remove event at c means coverage ended at c-1, so at point c the coverage is gone -> remove first, then add.
    # Wait: event (right+1, -1, C) means at coordinate right+1, remove C. At point right+1, this tower no longer covers.
    # event (left, +1, C) means at coordinate left, add C. At point left, this tower covers.
    # So at the same coordinate, if we have both remove and add:
    # The remove should happen first (since the removal is for coverage that ended at coord-1),
    # then adds. After both, the sum is correct for this coordinate.
    # Let me re-sort: removes (-1) before adds (+1) at same coordinate.
    
    events.sort(key=lambda e: (e[0], e[1]))  # -1 < 1, so removes come first. Good.
    
    current_sum = 0
    max_sum = 0
    
    for coord, typ, c in events:
        if typ == 1:
            current_sum += c
        else:
            current_sum -= c
        if current_sum > max_sum:
            max_sum = current_sum
    
    print(max_sum)

main()

---

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