概要

数直線上の座標 \(0\) から座標 \(L\) まで、Wi-Fiルーターの電波圏内（区間）だけを通って到達できるかを判定する問題です。これは「区間のカバー問題」として、貪欲法で効率的に解けます。

考察

問題の言い換え

各ルーターは区間 \([X_i - R_i, X_i + R_i]\) をカバーしています。問題は「これらの区間を使って、\([0, L]\) を連続的にカバーできるか」という問題に帰着できます。

素朴なアプローチの問題点

すべての区間の組み合わせを試すと、\(2^N\) 通りの選び方があり、\(N\) が大きい場合は計算が間に合いません（TLE）。

重要な気づき

貪欲法が有効です。現在いる位置から到達可能な区間の中で、最も右まで届く区間を選ぶのが最適です。

なぜなら、より右まで届く区間を選べば、次に選べる区間の選択肢が減ることはなく、むしろ増える可能性があるからです。

具体例

\(L = 10\) で、区間が \([0, 3], [2, 6], [5, 10]\) の場合： 1. 座標 \(0\) からスタート。\(0\) を含む区間 \([0, 3]\) により、座標 \(3\) まで到達可能 2. 座標 \(3\) 以下から始まる区間で最も右に届くのは \([2, 6]\)。座標 \(6\) まで到達可能 3. 座標 \(6\) 以下から始まる区間で最も右に届くのは \([5, 10]\)。座標 \(10\) まで到達可能 4. ゴール \(L = 10\) に到達！→ Yes

アルゴリズム

1. 各ルーターのカバー区間 \([X_i - R_i, X_i + R_i]\) を計算する
2. 区間を左端でソートする
3. 座標 \(0\) がカバーされているか確認（されていなければ No）
4. 貪欲法で右端を拡張：
   • current_pos（現在到達可能な最右端）を \(0\) で初期化
   • current_pos 以下から始まる区間の中で、最も右まで届く区間を選ぶ
   • その区間の右端を新しい current_pos とする
   • これを current_pos >= L になるまで繰り返す
5. 進めなくなったら No、\(L\) に到達できたら Yes

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 貪欲法のループは各区間を最大1回しか見ないため \(O(N)\)
• 空間計算量: \(O(N)\)
  • 区間を格納する配列に \(O(N)\)

実装のポイント

1. 区間の左端でソートする: これにより、「現在位置以下から始まる区間」を順番に効率的に処理できます

2. インデックス i を使い回す: ループの外で i を管理し、一度見た区間を再度見ないようにすることで、全体で \(O(N)\) を実現しています

3. 進めなくなった判定: best_right == current_pos のとき、どの区間を使っても前に進めないため No を出力します

4. 座標 \(0\) のカバー確認: スタート地点が電波圏内でなければ、そもそも移動を開始できないため、最初に確認が必要です

   ソースコード

def solve():
    N, L = map(int, input().split())
    
    intervals = []
    for _ in range(N):
        x, r = map(int, input().split())
        left = x - r
        right = x + r
        intervals.append((left, right))
    
    # 区間を左端でソート
    intervals.sort()
    
    # 座標0がカバーされているか確認
    # 現在到達可能な最右端を追跡
    current_right = 0
    
    # 座標0をカバーする区間があるか確認
    covers_start = False
    for left, right in intervals:
        if left <= 0 <= right:
            covers_start = True
            break
    
    if not covers_start:
        print("No")
        return
    
    # 貪欲法で最右端を拡張
    # 現在位置から到達可能な区間の中で、最も右まで届くものを選ぶ
    current_pos = 0
    i = 0
    
    while current_pos < L:
        # current_pos以下から始まる区間の中で、最も右まで届くものを探す
        best_right = current_pos
        
        while i < N and intervals[i][0] <= current_pos:
            best_right = max(best_right, intervals[i][1])
            i += 1
        
        # 進めなかった場合
        if best_right == current_pos:
            print("No")
            return
        
        current_pos = best_right
    
    # current_pos >= L なら到達可能
    print("Yes")

solve()

---

この解説は claude4.5opus によって生成されました。