概要

\(N\) 個の区間 \([l_i, l_i + w_i]\) が与えられるので、それらの和集合（重なりを除いた合計の長さ）を求める問題です。典型的な「区間のマージ（統合）」によって解くことができます。

考察

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

壁の幅 \(W\) は最大 \(10^9\) と非常に大きいため、壁を1マスずつ配列で管理して「塗られたかどうか」を記録する方法は、メモリも時間も到底足りません。

重要な気づき

テープの本数 \(N\) は最大 \(2 \times 10^5\) なので、区間そのものを直接扱う方が効率的です。

区間を左端でソートすると、重なっている区間を順番にまとめていく（マージする）ことができます。具体的には：

• 区間を左端の小さい順に見ていく
• 今注目している区間が、直前までの区間と重なっている（または隣接している）なら、1つの区間に統合する
• 重なっていなければ、直前の区間は確定するので長さを加算し、新しい区間を開始する

具体例

例えば、区間 \([1, 5]\), \([3, 7]\), \([10, 15]\) があるとします。

1. まず左端でソート → \([1,5], [3,7], [10,15]\)（既にソート済み）
2. \([1,5]\) を現在の区間とする
3. \([3,7]\)：左端 \(3 \leq 5\)（現在の右端）なので重なる → 区間を \([1, 7]\) に拡張
4. \([10,15]\)：左端 \(10 > 7\) なので重ならない → \([1,7]\) の長さ \(6\) を加算し、現在の区間を \([10,15]\) に更新
5. 最後に \([10,15]\) の長さ \(5\) を加算

合計：\(6 + 5 = 11\)

アルゴリズム

1. 各テープの区間 \([l_i, l_i + w_i)\) を作成する
2. 区間を左端 \(l_i\) の昇順でソートする
3. 最初の区間を「現在の区間」\((cur\_start, cur\_end)\) とする
4. 2番目以降の区間 \((s, e)\) について：
   • \(s \leq cur\_end\) ならば重なっているので、\(cur\_end = \max(cur\_end, e)\) に更新
   • そうでなければ、\(cur\_end - cur\_start\) を合計に加算し、\((cur\_start, cur\_end) = (s, e)\) に更新
5. ループ終了後、最後の区間の長さ \(cur\_end - cur\_start\) を合計に加算
6. 合計を出力

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック。マージの走査は \(O(N)\)）
• 空間計算量: \(O(N)\)（区間を格納するリスト）

実装のポイント

• 入力の高速化: \(N\) が最大 \(2 \times 10^5\) なので、sys.stdin.read() でまとめて読み込むことで入力を高速化しています。

• 区間の表現: 入力では「左端 \(l_i\) と長さ \(w_i\)」が与えられますが、右端を \(l_i + w_i\) として計算し、区間 \((l_i, l_i + w_i)\) のペアとして管理します。

• 最後の区間の処理を忘れない: ループ内では「新しい区間が始まるとき」に前の区間を加算するため、ループ終了後に最後の区間の長さを加算する処理が必要です。これを忘れると答えが小さくなってしまいます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    intervals = []
    for i in range(N):
        l = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        intervals.append((l, l + w))
    
    intervals.sort()
    
    total = 0
    cur_start, cur_end = intervals[0]
    
    for i in range(1, N):
        s, e = intervals[i]
        if s <= cur_end:
            cur_end = max(cur_end, e)
        else:
            total += cur_end - cur_start
            cur_start, cur_end = s, e
    
    total += cur_end - cur_start
    print(total)

main()

---

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