概要

連続した区間の基地を選び、その区間に含まれる基地のコスト合計が予算以内であるような条件下で、区間の長さ（右端−左端）の最大値を求める問題です。

考察

この問題は典型的な「尺取り法（しゃくとり法）」またはスライディングウィンドウと呼ばれるアルゴリズムが適用できます。

重要な観察

• 基地は直線上に位置しており、位置は昇順に与えられる： \(X_1 < X_2 < \cdots < X_N\)
• 区間 \([l, r]\) を選ぶとき、その区間の長さは \(X_r - X_l\)
• 選んだ区間のコストの合計 \(\sum_{i=l}^{r} C_i\) が予算 \(M\) 以下であれば良い

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

全探索によって、すべての区間 \([l, r]\) を試すことを考えると、計算量は \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) に対しては明らかに時間内に終わりません（TLE）。

さらに、単純な二分探索などでも「固定した左端に対して右端をどこまで伸ばせるか」を毎回調べるのは非効率です。

解決策：尺取り法の利用

尺取り法を使うことで、区間の左端と右端を動的に管理しながら、条件を満たす最大の区間長を求めることができます。

具体的には： - 右端をどんどん伸ばしていき、予算を超えるまで区間を広げる - 予算を超えたら、左端を縮めてコストを削減する - 各状態でコストが予算内なら、その区間の長さを記録

これにより、各要素を一度ずつしか見ないので、計算量が \(O(N)\) になります。

アルゴリズム

1. 左右のポインタ（尺取りの窓）を持つ。初期状態では両方とも先頭。
2. 右端を1つずつ進めながら、その基地のコストを合計に加える。
3. 合計コストが予算 \(M\) を超えた場合、左端を進めてコストを減らす。
4. コストが予算内であれば、現在の区間の長さ \(X_r - X_l\) を計算し、最大値を更新。
5. 右端が最後まで行ったら終了。

この処理を双方向キュー（deque）を使って実装することで、区間の追加・削除が効率的に行えます。

例

入力例：

5 10
1 2
3 3
5 1
7 4
9 2

コストの合計が予算を超えない範囲で区間を広げていき、例えば区間 \([1, 5]\) まで選べばコストは \(2+3+1+4+2=12\) でオーバーなので、左を縮めます。最終的に最長となる区間を見つけます。

計算量

• 時間計算量: \(O(N)\)
  各要素が高々1回追加・削除されるため。
• 空間計算量: \(O(N)\)
  dequeに最大で \(N\) 個の要素が格納される。

実装のポイント

• deque を使うことで、左右からの追加・削除が効率的に行える。
• 左端を削除する際は、合計コストからその基地のコストを引くのを忘れない。
• 区間が空になった場合（len(dq) == 0）は長さを更新しないように注意。
• total_cost <= M の判定を毎ステップ行い、条件を満たす場合に限り長さを計算。

## ソースコード

```python
import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    X = [0] * N
    C = [0] * N
    
    index = 2
    for i in range(N):
        X[i] = int(data[index])
        C[i] = int(data[index+1])
        index += 2

    # 双方向キューを用いたアプローチ
    max_length = 0
    dq = deque()
    total_cost = 0

    for i in range(N):
        # 新しい要素を右端に追加
        dq.append((X[i], C[i]))
        total_cost += C[i]

        # 予算を超えないように左端を調整
        while total_cost > M and dq:
            _, cost = dq.popleft()
            total_cost -= cost

        # 現在の区間が有効であれば最大長を更新
        if total_cost <= M and len(dq) >= 1:
            current_length = dq[-1][0] - dq[0][0]
            if current_length > max_length:
                max_length = current_length

    print(max_length)

if __name__ == "__main__":
    main()

---

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