概要

与えられた \(N\) 本のテープ区間 \([l_i, l_i+w_i]\) の重なりをまとめて、壁のうち「少なくとも1本貼られている部分」の合計長（和集合の長さ）を求めます。

考察

各テープは数直線上の区間として扱えます。求めたいのは区間の和集合の長さなので、重なっている部分を二重に数えないようにする必要があります。

素朴な方法がダメな理由

• 壁の幅 \(W\) は最大 \(10^9\) なので、1マスずつ塗られているかを配列で管理するような方法はメモリ的にも時間的にも不可能です。
• 区間同士の重なりを全組み合わせで調べると \(O(N^2)\) になり、\(N \le 2\times10^5\) ではTLEになります。

重要な気づき

区間を左端でソートすると、左から順に見ていくだけで - 「今の区間と重なるか」 - 「重ならないなら、そこで1つのまとまりが確定する」 が判定でき、重なりを自然に統合できます。

例えば区間が
\([1,4],[2,6],[8,10]\) のとき（ソート済み）、 - 最初の2つは重なるので \([1,6]\) に統合 - 次の \([8,10]\) は離れているので、\([1,6]\) の長さ \(5\) を加算し、新しいまとまり開始
最終的に \(5 + 2 = 7\) が答えになります。

アルゴリズム

1. 各テープを区間 \((l_i, r_i)=(l_i, l_i+w_i)\) として配列に格納する。
2. 区間を左端 \(l\) の昇順でソートする。
3. ソート後、左から順に見て「現在統合中の区間」\([cur_l, cur_r]\) を管理する。
   • 次の区間 \([l,r]\) が \(l \le cur_r\) を満たすなら重なる（または端で接する）ので、\(cur_r=\max(cur_r,r)\) として統合する。
   • そうでなければ重ならないので、いままでのまとまりの長さ \(cur_r-cur_l\) を答えに加算し、\([cur_l,cur_r]=[l,r]\) に更新する。
4. ループ終了後、最後のまとまり \(cur_r-cur_l\) も加算して出力する。

この方法で、重なり部分を二重カウントせずに和集合の長さを求められます。

計算量

• 時間計算量: \(O(N\log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（区間配列を保持）

実装のポイント

• 区間は \((l, l+w)\) に変換して扱うと分かりやすいです。

• 判定条件は \(l \le cur_r\)（重なる／接する）でOKです。接している場合（例: \([0,2]\) と \([2,5]\)）も和集合としては連続なので統合して問題ありません。

• Pythonでは \(N\) が大きいので sys.stdin.buffer.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, W = map(int, input().split())
    intervals = []
    for _ in range(N):
        l, w = map(int, input().split())
        intervals.append((l, l + w))

    intervals.sort()
    total = 0
    cur_l, cur_r = intervals[0]

    for l, r in intervals[1:]:
        if l <= cur_r:
            if r > cur_r:
                cur_r = r
        else:
            total += cur_r - cur_l
            cur_l, cur_r = l, r

    total += cur_r - cur_l
    print(total)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。