概要

この問題は、数直線上の座標 \(0\) から \(L\) までの区間が、与えられた \(N\) 個のWi-Fiルーターのカバー範囲（区間）によって途切れなく連結されているかを判定する問題です。

考察

高橋君が座標 \(0\) から \(L\) まで移動するためには、「現在いる地点がWi-Fiの範囲内であること」と「次に進む地点もWi-Fiの範囲内であること」が必要です。これは、座標 \(0\) から出発して、電波の届く範囲が隙間なく座標 \(L\) まで繋がっている必要があると言い換えられます。

各ルーター \(i\) がカバーする範囲は、区間 \([X_i - R_i, X_i + R_i]\) です。この問題の難しい点は、ルーターが設置されている順番とカバー範囲がバラバラであることです。

効率的な解法の検討

もし、すべての区間を単純に結合しようとすると、計算量が増えてしまいます。しかし、「左端（座標 \(0\)）から順にどこまで到達できるか」に注目すると、効率的に解くことができます。

1. まず、各ルーターの範囲を \([start, end]\) という形式の区間に変換します。
2. これらの区間を「開始地点 (\(start\))」が小さい順に並べます（ソート）。
3. 現在の到達可能な最大座標を current_max_reach とし、最初は \(0\) とします。
4. ソートされた区間を一つずつ確認し、その区間の開始地点が current_max_reach 以下であれば、その区間を使ってさらに遠くへ（end まで）到達できる可能性があります。

もし、次に確認する区間の開始地点が current_max_reach よりも後ろにある場合、そこに「電波の届かない隙間」が存在することになり、それ以上先へは進めません。

アルゴリズム

この問題は、貪欲法（Greedy Algorithm）とソートを組み合わせて解くことができます。

1. 区間の作成: 各ルーター \(i\) について、区間 \([X_i - R_i, X_i + R_i]\) を計算し、リストに格納します。
2. ソート: リストを開始地点 \(start\) の昇順でソートします。
3. 範囲の拡張:
   • current_max_reach = 0 と初期化します。
   • 各区間 \([start, end]\) について以下を繰り返します：
     • もし start <= current_max_reach ならば、現在の到達範囲を max(current_max_reach, end) に更新します。
     • もし start > current_max_reach ならば、隙間があるためループを終了します。
4. 判定: 最終的な current_max_reach が \(L\) 以上であれば Yes、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の区間の作成に \(O(N)\)、それらのソートに \(O(N \log N)\)、リストの走査に \(O(N)\) かかります。全体のボトルネックはソート部分です。
• 空間計算量: \(O(N)\)
  • \(N\) 個のルーターの情報を区間として保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 座標 0 の判定: 最初のルーターの開始地点が \(0\) 以下でない限り、current_max_reach は \(0\) から増えません。これにより「座標 \(0\) が圏内である必要がある」という条件も自然に満たされます。

• ソートの重要性: 開始地点でソートすることで、一度の走査で「隙間があるかどうか」を確実に判定できるようになります。

• 大きな値の扱い: \(L\) や \(R_i\) が最大 \(10^9\) と大きいため、座標を配列の添字として使うような解法（バケットなど）はメモリ不足になるため避け、区間として処理する必要があります。

  ソースコード

import sys

def solve():
    # 標準入力から全データを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: ルーターの数, L: ゴールの座標
    N = int(input_data[0])
    L = int(input_data[1])
    
    # 各ルーターのカバー範囲を [開始地点, 終了地点] の区間としてリストに格納
    intervals = []
    for i in range(N):
        x = int(input_data[2 + 2 * i])
        r = int(input_data[3 + 2 * i])
        intervals.append((x - r, x + r))
    
    # 区間の開始地点で昇順にソート
    intervals.sort()
    
    # 現在、座標0から連続して到達可能な最大の座標
    current_max_reach = 0
    
    # 各区間を順番に確認し、連続した範囲を広げていく
    for start, end in intervals:
        # 現在の到達可能範囲の末端よりも、次の区間の開始地点が後ろにある場合は隙間がある
        if start <= current_max_reach:
            # 隙間がない場合、到達可能範囲を更新する
            if end > current_max_reach:
                current_max_reach = end
        else:
            # 隙間が見つかった時点で、これ以上先には進めない
            break
            
    # 到達可能な最大座標がゴールの座標 L 以上であれば到達可能
    if current_max_reach >= L:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。