概要

各ルーターの電波範囲を区間として考え、それらの和集合が \([0, L]\) を途切れなく覆えるかを判定する問題です。

考察

高橋君が「常にWi-Fiに接続されている場所にしか進めない」という条件は、言い換えると

• 通れる場所 = ルーターの電波範囲（区間）の和集合
• ゴールできる = \(0\) から \(L\) までを途切れずに進める

つまり、区間の和集合が \([0, L]\) を連結に覆っているか（途中に穴がないか）を見ればよいです。
途中に少しでも電波の届かない隙間（ギャップ）があると、その先へは進めません。

素朴に「座標を少しずつ動かしてシミュレーション」しようとすると、\(L\) が最大 \(10^9\) なので到底間に合いません（TLE）。
そこで、座標を直接なめるのではなく、区間をソートして貪欲に連結していくことで高速に判定します。

アルゴリズム

各ルーター \(i\) の電波範囲を区間 $\([X_i - R_i,\; X_i + R_i]\)$ として扱います。

1. すべての区間を左端で昇順ソートする。
2. 現在「到達できる右端」を reach として管理する（初期値 reach = 0）。
3. ソートした区間を左から順に見ていく：
   • もし区間の左端が l > reach なら、reach から次の区間までにギャップがあるので到達不能（そこで終了）。
   • そうでなければ、その区間で右端を伸ばせるので reach = max(reach, r) とする。
   • reach >= L になった時点で \(L\) に到達可能なので Yes。
4. 最後まで見ても reach < L なら No。

具体例

\([0,3]\), \([2,5]\), \([6,10]\) のような区間があるとき、 - 最初の2つで到達範囲は \(0 \to 5\) まで伸びるが、 - 次の区間は左端が \(6\) で 6 > 5 となりギャップがある
→ そこで進めなくなり No。

この方法は「今つながっている範囲を可能な限り右へ伸ばす」貪欲法で、区間の連結判定の典型です。

計算量

• 時間計算量: ソートが支配的で \(O(N \log N)\)
• 空間計算量: 区間配列に \(O(N)\)

実装のポイント

• reach を \(0\) にしておくと、座標 \(0\) が電波圏内でない場合は最初の区間で l > reach となり自然に No になります（問題文の条件「\(0\) も電波圏内」が満たせない）。

• 区間の左端は \(X_i - R_i\) なので負になり得ますが、そのままでOKです（ソートして貪欲に処理すれば問題なし）。

• reach >= L を満たしたら即 Yes を出して早期終了すると無駄がありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, L = map(int, input().split())
    intervals = []
    for _ in range(N):
        x, r = map(int, input().split())
        intervals.append((x - r, x + r))

    intervals.sort()

    reach = 0
    for l, r in intervals:
        if l > reach:
            break
        if r > reach:
            reach = r
        if reach >= L:
            print("Yes")
            return

    print("Yes" if reach >= L else "No")

if __name__ == "__main__":
    main()

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