概要

直線上に配置された複数の電波塔のカバー範囲（区間）と、それぞれの信号強度（重み）が与えられたとき、どの地点に立てば受信できる信号強度の合計を最大化できるかを求める問題です。

考察

この問題は、「重み付き区間が最も重なり合っている地点の重みの合計を求める」と言い換えることができます。

素朴なアプローチ

すべての整数座標について信号強度を計算しようとすると、座標の範囲が \(0\) から \(10^9\) 以上に及ぶため、計算が終わらず実行時間制限（TLE）になってしまいます。

重要な気づき

信号強度の合計が変化するのは、いずれかの電波塔のカバー範囲が始まる地点、または終わる地点だけです。 塔 \(i\) のカバー範囲は \([X_i - L_i, X_i + R_i]\) です。したがって、合計値が変化する候補は以下の座標に絞られます。 - 範囲の開始：\(X_i - L_i\) - 範囲の終了の直後：\(X_i + R_i + 1\)

これら以外の地点では、隣の座標に移動しても合計強度は変わりません。そのため、これらの「イベントが発生する座標」だけを効率よく処理すれば、最大値を求めることができます。

アルゴリズム

「いもす法」や「走査線（スイープ法）」と呼ばれる手法を用います。

1. イベントの列挙: 各電波塔 \(i\) について、以下の 2 つのイベントを作成します。
   • 座標 \(X_i - L_i\) で強度 \(C_i\) を加算する。
   • 座標 \(X_i + R_i + 1\) で強度 \(C_i\) を減算する。
2. ソート: 作成したすべてのイベントを座標の昇順に並べ替えます。
3. 走査（スイープ）: ソートされたイベントを端から順番に見ていき、現在の信号強度の合計（current_strength）を更新していきます。
   • 同じ座標に複数のイベントがある場合は、それらをすべて合算した後に最大値を判定します。
   • 各ステップで current_strength の最大値を記録します。

計算量

• 時間計算量: \(O(N \log N)\) イベントの数は \(2N\) 個です。これらをソートするのに \(O(N \log N)\) かかります。その後の走査は \(O(N)\) で終わるため、全体の計算量はソートが支配的になります。
• 空間計算量: \(O(N)\) \(2N\) 個のイベントをリストに保持するためのメモリが必要です。

実装のポイント

• 範囲の終端: 問題文では「\(X_i + R_i\) 以下の範囲をカバーする」とあるため、強度が減少するのはその次の座標である \(X_i + R_i + 1\) です。

• 同じ座標のイベント: 同じ座標で「開始」と「終了」が同時に発生する場合、それらをまとめて処理してから最大値を更新するようにします。Pythonのコードでは while ループを使って同じ座標のイベントを一括処理しています。

• 高速な入力: \(N\) が \(10^5\) と大きいため、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が実行時間を短縮できます。

  ソースコード

import sys

# 競技プログラミングのエキスパートとして、以下の問題を解くコードを実装します。
# 道路上の任意の整数座標において、受信できる信号の強度の合計を最大化する問題です。
# 各電波塔 i のカバー範囲は [X_i - L_i, X_i + R_i] で、その強度は C_i です。
# この問題は、重み付き区間の最大重み地点を見つける問題として、
# スイープ法（平面走査法）を用いて O(N log N) で解くことができます。

def solve():
    # 標準入力からすべてのデータを読み込みます。
    # 大量のデータを扱うため、sys.stdin.read().split() を使用して高速にパースします。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 電波塔の数 N
    N = int(input_data[0])
    
    # イベントを格納するリスト。各イベントは (座標, 強度の変化) のタプルです。
    events = []
    
    # 各電波塔のデータをパースし、イベントを作成します。
    # 電波塔 i は [X_i - L_i, X_i + R_i] の範囲をカバーします。
    for i in range(N):
        base_idx = 1 + i * 4
        x = int(input_data[base_idx])
        l = int(input_data[base_idx + 1])
        r = int(input_data[base_idx + 2])
        c = int(input_data[base_idx + 3])
        
        # 座標 (x - l) で信号強度 c が加算されます。
        events.append((x - l, c))
        # 座標 (x + r) まで信号が届くため、(x + r + 1) で信号強度 c が減算されます。
        events.append((x + r + 1, -c))
        
    # イベントを座標の昇順にソートします。
    # 同じ座標に複数のイベントがある場合でも、まとめて処理することで正しく計算できます。
    events.sort()
    
    max_strength = 0
    current_strength = 0
    
    i = 0
    num_events = len(events)
    
    # スイープラインを動かして最大値を求めます。
    while i < num_events:
        curr_x = events[i][0]
        
        # 同じ座標で発生するすべてのイベント（信号の開始・終了）を合算します。
        # これにより、その座標における正確な合計信号強度が得られます。
        while i < num_events and events[i][0] == curr_x:
            current_strength += events[i][1]
            i += 1
        
        # 現在の座標における合計強度がこれまでの最大値を超えていれば更新します。
        if current_strength > max_strength:
            max_strength = current_strength
            
    # 最終的な最大信号強度を出力します。
    sys.stdout.write(str(max_strength) + '\n')

if __name__ == '__main__':
    solve()

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