概要

複数のマスキングテープが貼られた壁において、少なくとも1本のテープが貼られている部分の合計長さ（区間の和集合の長さ）を求める問題です。

考察

この問題は、N個の区間 \([l_i, l_i + w_i]\) の和集合の長さを求める問題です。素朴なアプローチとして、壁全体を配列で表現して各テープがカバーする範囲をマークする方法が考えられますが、Wが最大 \(10^9\) と非常に大きいため、メモリ制限と計算時間の観点から不可能です。

代わりに、区間を効率的にマージする方法を考える必要があります。区間を開始位置でソートし、隣接する区間が重なるかどうかを確認しながらマージしていくことで、重複を排除した合計長さを計算できます。

アルゴリズム

1. すべての区間を開始位置 \(l_i\) でソートします
2. 最初の区間を現在のマージ区間として設定します
3. ソートされた区間を順に処理します：
   • 現在の区間が次の区間と重なる場合（次の区間の開始位置が現在の終了位置以下）、現在の終了位置を拡張します
   • 重ならない場合、現在の区間の長さを合計に加算し、次の区間を新しい現在の区間として設定します
4. 最後に残っている現在の区間の長さを合計に加算します

このアルゴリズムは区間スケジューリング問題などでよく使われる手法で、重複する区間を効率的にマージできます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートの計算量が支配的）
• 空間計算量: \(O(N)\)（区間を格納するためのメモリ）

実装のポイント

• 区間の終了位置を比較する際、max関数を使って現在の終了位置を拡張する必要があります

• 最後の区間を処理した後、マージ中の区間を忘れずに合計に加算することが重要です

• 入力値が整数であるため、浮動小数点数の精度問題を気にする必要がありません

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    W = int(data[1])
    intervals = []
    index = 2
    for i in range(n):
        l = int(data[index])
        w = int(data[index+1])
        index += 2
        intervals.append((l, l + w))
    
    intervals.sort(key=lambda x: x[0])
    
    total = 0
    current_start, current_end = intervals[0]
    
    for i in range(1, n):
        if intervals[i][0] <= current_end:
            current_end = max(current_end, intervals[i][1])
        else:
            total += current_end - current_start
            current_start, current_end = intervals[i]
    
    total += current_end - current_start
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。