概要

連続する基地区間 \([l,r]\) を選び、費用合計が予算 \(M\) 以下となる範囲で、敷設できる回線の長さ \(X_r - X_l\) を最大化する問題です。

考察

• 選ぶ区間は 連続 でなければならず、区間の費用は \(\sum_{i=l}^{r} C_i\)、長さは \(X_r - X_l\) です。
• したがって「費用合計が \(M\) 以下」という制約のもとで、\(X_r - X_l\) を最大化する 部分配列（連続区間） 問題になります。

素朴な方法が遅い理由

• すべての \((l,r)\) を試すと区間数は \(O(N^2)\) 個あります。
• \(N \le 2\times 10^5\) なので、\(N^2\) は最大で \(4\times 10^{10}\) となり現実的な時間で終わりません（TLE）。

重要な気づき

• \(C_i \ge 1\) なので、右端 \(r\) を右に伸ばすと区間の費用合計は 単調に増える（減らない）。
• もし費用が \(M\) を超えたら、左端 \(l\) を右に動かして区間を縮めれば費用は減る。
• この「右端は右へ、超えたら左端も右へ」という動きは、各ポインタが最大でも \(N\) 回しか動かないため、全体を \(O(N)\) で処理できます。

アルゴリズム

しゃくとり法（Two Pointers / Sliding Window） を使います。

1. 左端 \(l=0\)、区間費用の合計 \(s=0\)、答え \(ans=0\) で初期化する。
2. 右端 \(r\) を \(0\) から \(N-1\) まで順に動かす。
   • \(s \leftarrow s + C_r\) として区間 \([l,r]\) を広げる。
   • もし \(s > M\) なら、条件を満たすまで以下を繰り返す：
     • \(s \leftarrow s - C_l\)
     • \(l \leftarrow l + 1\)
   • 条件 \(s \le M\) を満たしたら、このときの長さ \(X_r - X_l\) で \(ans\) を更新する。
3. 最終的に \(ans\) を出力する。

簡単な例

費用合計が超えたら左を縮めるイメージです： - \(r\) を進めて区間が大きくなる → 費用が増える - 予算超過したら \(l\) を進めて区間を小さくする → 費用が減る - 条件を満たした時点の \(X_r - X_l\) が、その \(r\) に対して取り得る最大級の長さ候補になる

計算量

• 時間計算量: \(O(N)\)
  （\(l\) と \(r\) はそれぞれ高々 \(N\) 回しか増えないため）
• 空間計算量: \(O(N)\)
  （\(X, C\) 配列を保持するため）

実装のポイント

• \(M\) は最大 \(10^{14}\)、\(\sum C_i\) も大きくなり得るので、合計 \(s\) は 64bit 整数 で扱う必要があります（Pythonなら通常の int でOK）。

• while で s > M の間縮めることで、常に「費用合計が \(M\) 以下の最小の \(l\)」を維持できます。

• \(l=r\) の場合でも長さは \(X_r - X_l = 0\) となり、そのまま扱って問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    X = [0] * N
    C = [0] * N
    for i in range(N):
        x, c = map(int, input().split())
        X[i] = x
        C[i] = c

    l = 0
    s = 0
    ans = 0

    for r in range(N):
        s += C[r]
        while l <= r and s > M:
            s -= C[l]
            l += 1
        if l <= r:
            ans = max(ans, X[r] - X[l])

    print(ans)

if __name__ == "__main__":
    main()

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