概要

数直線上の区間をカバーするWi-Fiルーターがあり、始点 \(0\) から終点 \(L\) まで移動する際に、常に少なくとも1つのルーターの電波圏内を保ちながら移動可能かどうかを判定する問題。

考察

この問題では、それぞれのWi-Fiルーターがカバーする区間 \([X_i - R_i, X_i + R_i]\) が与えられ、これらの区間によって数直線の一部が覆われています。高橋君は、連続的にカバーされた領域を渡って移動しなければならないため、区間の「隙間」があると到達できません。

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

例えば、すべての区間を愚直にマージして、最終的に \([0, L]\) が完全に含まれるか調べる方法があります。しかし、区間が多い場合（最大 \(2 \times 10^5\)）、無駄が多く時間がかかります。

また、区間の端点が非常に大きい（最大 \(10^9\)）ため、区間をビットなどで管理することも不可能です。

解決策：貪欲法による区間スケジューリング

この問題は典型的な区間スケジューリング問題の亜種と考えることができます。区間をソートして、今カバーしている範囲の終端を最大限伸ばせる区間を選ぶ戦略が有効です。

具体的には、以下のように進めます： 1. 各ルーターのカバー範囲を区間 \([l_i, r_i]\) として計算し、開始位置 \(l_i\) で昇順にソート。 2. 最初に、区間の開始が \(0\) 以降になっていないか確認（\(0\) がカバーされていなければ即 No）。 3. 現在カバーしている範囲の終端 current_end を管理しながら、その中からさらに伸ばせる最も遠い終端を持つ区間を選んでいく。 4. current_end が \(L\) 以上になったら成功。

このように、「次の選択肢の中で、最も遠くまでカバーできるものを使う」という貪欲法により、最適解が得られます。

アルゴリズム

1. 各ルーターのカバー範囲 \([X_i - R_i, X_i + R_i]\) を計算し、\((開始位置, 終了位置)\) のペアとしてリストに格納。
2. 開始位置の昇順で区間をソート。
3. 最初の区間が \(0\) を含まない場合、No を出力。
4. current_end = 0 とし、左から区間を見ていく：
   • 現在の区間の開始位置が current_end よりも大きい場合 → 隙間があるため No。
   • そうでない限り、開始位置が current_end 以下の区間の中から、最も遠い終了位置を持つものを選び、current_end を更新。
5. current_end >= L になった時点で Yes を出力。
6. 全区間を見た後でも到達できていなければ No。

例

入力例：

3 10
2 3
5 2
8 3

区間は： - \([2-3, 2+3] = [-1, 5]\) - \([5-2, 5+2] = [3, 7]\) - \([8-3, 8+3] = [5, 11]\)

これらを開始位置でソートすると： - \([-1, 5]\) - \([3, 7]\) - \([5, 11]\)

処理の流れ： 1. current_end = 0。最初の区間 \([-1, 5]\) で更新 → current_end = 5 2. 次の区間 \([3, 7]\) は使用可能 → current_end = 7 3. 次の区間 \([5, 11]\) も使用可能 → current_end = 11 4. 11 >= 10 なので Yes

計算量

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

実装のポイント

• 区間を \((開始位置, 終了位置)\) として前処理し、開始位置でソートするのが重要。
• current_end を使いながら、どの区間までカバーできるかを逐次更新。
• 最初の区間が \(0\) をカバーしていない場合や、途中でギャップがある場合はすぐに No を出力。
• 高速な入力処理（sys.stdin.readなど）が必要（特にPythonでは推奨）。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    L = int(data[1])
    
    routers = []
    index = 2
    for _ in range(N):
        x = int(data[index])
        r = int(data[index+1])
        routers.append((x - r, x + r))
        index += 2
    
    # 区間を開始位置でソート
    routers.sort()
    
    # 座標0をカバーする区間があるか確認
    if not routers or routers[0][0] > 0:
        print("No")
        return
    
    current_end = 0
    i = 0
    
    while i < N:
        # 現在カバーしている範囲から次に伸ばせる最も遠い範囲を探す
        if routers[i][0] > current_end:
            # ギャップがある場合到達不可
            print("No")
            return
        
        max_reach = current_end
        while i < N and routers[i][0] <= current_end:
            max_reach = max(max_reach, routers[i][1])
            i += 1
        
        current_end = max_reach
        
        if current_end >= L:
            print("Yes")
            return
    
    # 最後に到達できなかった場合
    print("No")

if __name__ == "__main__":
    main()

---

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