概要

\(N\) 本のマスキングテープが壁に貼られたとき、少なくとも1本以上のテープがかかっている壁の部分の長さの合計を求めます。

考察

この問題は、与えられた \(N\) 個の区間の和集合の長さを求めることに他なりません。
例えば、以下のような区間があるとします：

• 区間A: [1, 4]
• 区間B: [3, 6]
• 区間C: [8, 10]

これらを数直線上にプロットすると、AとBは重なっているので連結し、[1, 6] という1つの連続領域になります。Cは独立しています。したがって、答えは \((6 - 1) + (10 - 8) = 5 + 2 = 7\) となります。

素朴な方法（例えば、壁の各座標を1つずつ見ていく）では、壁の幅 \(W\) が最大 \(10^9\) あるため、TLE（時間超過）になってしまいます。

この問題を効率的に解くには、区間を統合して重複を除き、その後その統合された区間の長さを合計すればよいです。
区間の統合を行う前に区間を開始位置でソートしておくことで、隣接または重なっている区間を順番にマージしていくことができます。

アルゴリズム

1. 各テープの貼られている区間 \([l_i, l_i + w_i]\) をリストに格納します。
2. このリストを区間の開始位置 \(l_i\) で昇順にソートします。
3. ソートされた区間に対して、次のようにして統合を行います：
   • 結果を格納するリスト merged を用意します。
   • 各区間について、それが前の区間と重なるかどうかを判定します：
     • 重ならない場合（現在の区間の開始位置が、前区間の終了位置より大きい）、新しい区間として追加します。
     • 重なる場合は、前区間の終了位置を現在の区間の終了位置に拡張します（ただし、より大きい方を選びます）。
4. 最後に、merged に残った区間それぞれの長さ（\(end - start\)）を合計して出力します。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。

• 区間の終了位置は \(l_i + w_i\) であり、区間は半開区間 \([l_i, l_i + w_i)\) ではなく閉区間 \([l_i, l_i + w_i]\) として扱います。

• 最後の区間のマージ時に max を使うことで、完全に包含されるようなケースも正しく処理できます。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    W = int(data[1])
    intervals = []
    index = 2
    for _ in range(N):
        l = int(data[index])
        w = int(data[index+1])
        intervals.append((l, l + w))
        index += 2

    # 区間を開始位置でソート
    intervals.sort()

    # 区間の統合
    merged = []
    for start, end in intervals:
        if not merged or merged[-1][1] < start:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)

    # 統合された区間の長さの合計を計算
    total = 0
    for start, end in merged:
        total += end - start

    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。