概要

この問題は、数直線上の与えられた \(N\) 個の区間 \([l_i, l_i + w_i]\) の和集合（少なくとも1つの区間に含まれる部分）の合計の長さを求める問題です。

考察

まず、壁の横幅 \(W\) が最大で \(10^9\) と非常に大きいため、「長さ \(W\) の配列を用意して、テープが貼られた場所にフラグを立てる」という手法はメモリ不足（MLE）や実行時間制限（TLE）のため使えません。

そこで、区間の重なりを効率的に処理する必要があります。

複数の区間が重なっている場合、それらをひとまとめの「大きな区間」として結合（マージ）することで、重複を排除して長さを計算できます。 例えば、区間 \([1, 5]\) と \([3, 7]\) があるとき、これらは重なっているため、結合すると \([1, 7]\) という1つの区間になり、長さは \(7 - 1 = 6\) と求まります。

このように効率よくマージを行うためには、区間を開始位置 \(l_i\) の昇順でソートするのが定石です。

アルゴリズム

「区間スケジューリング」に近い考え方で、以下の手順で解くことができます。

1. データの整形: 各テープの情報を、開始地点 \(l_i\) と終了地点 \(r_i = l_i + w_i\) のペア \((l_i, r_i)\) としてリストに格納します。
2. ソート: リストを開始地点 \(l_i\) の小さい順にソートします。
3. 走査とマージ:
   • 現在注目している「マージ中の区間」を [current_start, current_end] とします。最初は1番目の区間に設定します。
   • 2番目以降の各区間 [next_l, next_r] について、順番に以下の判定を行います。
     • 重なりがある場合 (next_l <= current_end): 次の区間の開始地点が、現在の区間の終了地点より前（または同じ位置）にあるなら、これらは繋がっています。現在の区間の終了地点を max(current_end, next_r) に更新します。
     • 重なりがない場合 (next_l > current_end): 次の区間とは離れているため、現在の区間の確定した長さ current_end - current_start を合計に加算します。その後、次の区間を新たな「マージ中の区間」として更新します。
4. 最後の処理: ループ終了後、最後に残っている「マージ中の区間」の長さを加算して完了です。

計算量

• 時間計算量: \(O(N \log N)\)
  • テープの情報をリストに格納するのに \(O(N)\)。
  • 開始地点でのソートに \(O(N \log N)\)。
  • ソート済みリストを1回走査してマージするのに \(O(N)\)。
  • 全体としてソートが支配的になります。
• 空間計算量: \(O(N)\)
  • \(N\) 個の区間情報を保持するためのリストが必要です。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と多いため、Pythonでは sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• ソートの基準: Pythonの sort() はタプルのリストに対して、1番目の要素（開始地点）を優先し、同じなら2番目の要素（終了地点）を比較するため、そのまま intervals.sort() と書くだけで適切な順序になります。

• 空の入力への配慮: 問題の制約上 \(N \geq 1\) ですが、念のためデータが空の場合の処理を入れておくと堅牢です。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: テープの本数, W: 壁の横幅
    N = int(input_data[0])
    W = int(input_data[1])
    
    # 各テープの区間 [l_i, l_i + w_i] をリストに格納する
    intervals = []
    idx = 2
    for _ in range(N):
        l = int(input_data[idx])
        w = int(input_data[idx+1])
        intervals.append((l, l + w))
        idx += 2
        
    if not intervals:
        print(0)
        return

    # 区間の開始位置で昇順にソートする
    intervals.sort()
    
    total_length = 0
    # 最初の区間を現在のマージ対象とする
    current_start, current_end = intervals[0]
    
    # 2番目以降の区間を順番に見て、重なりや隣接を確認しながらマージする
    for i in range(1, N):
        next_l, next_r = intervals[i]
        
        # 次の区間の開始位置が、現在の区間の終了位置以下であれば重なっている（または接している）
        if next_l <= current_end:
            # 現在の区間の終了位置を更新する
            if next_r > current_end:
                current_end = next_r
        else:
            # 重なりが途切れた場合、これまでの区間の長さを加算する
            total_length += current_end - current_start
            # 新しい区間を現在のマージ対象とする
            current_start = next_l
            current_end = next_r
    
    # 最後の区間の長さを加算する
    total_length += current_end - current_start
    
    # 結果を出力
    print(total_length)

if __name__ == '__main__':
    solve()

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