概要

一直線上に並んだ基地の中から、合計費用が予算 \(M\) 万円以内となるような連続する区間 \([l, r]\) を選び、その区間の長さ \(X_r - X_l\) の最大値を求める問題です。

考察

この問題を解くための重要なポイントは、「選ぶ区間を右に広げれば広げるほど、必要な費用の総額は増えていく」という単調性に注目することです。

もし、ある区間 \([l, r]\) の費用が予算 \(M\) を超えていないのであれば、その左端 \(l\) を固定したまま \(r\) をさらに大きくするか、あるいは \(l\) を右に動かして区間を短くすることで、別の有効な区間を探索できます。

なぜ素朴な方法ではダメなのか

すべての区間の組み合わせ \((l, r)\) を試す素朴な方法（二重ループ）では、区間の数が \(O(N^2)\) 個存在します。\(N = 2 \times 10^5\) であるため、組み合わせの数は最大で \(4 \times 10^{10}\) 通りとなり、実行時間制限に間に合いません。

そこで、左端 \(l\) を 1 つずつ動かしながら、それに対応する右端 \(r\) を効率よく管理する手法が必要になります。

アルゴリズム

尺取り法 (Two-pointer approach)

区間の左端を \(l\)、右端を \(r\) としたとき、以下の手順で最適な区間を探索します。

1. 右端を伸ばす: 現在の区間の合計費用に \(C_r\) を加えても予算 \(M\) を超えない限り、\(r\) を 1 つずつ進めていきます。
2. 最大値の更新: これ以上 \(r\) を進められなくなったら、その時の区間 \([l, r-1]\) の長さ \(X_{r-1} - X_l\) を計算し、暫定の最大値と比較して更新します。
3. 左端を縮める: \(l\) を 1 つ右に進めます。この際、合計費用から \(C_l\) を差し引きます。
4. 1〜3 を \(l\) が \(N\) に達するまで繰り返します。

この方法では、\(l\) も \(r\) もそれぞれ最大 \(N\) 回しか移動しないため、計算量を大幅に削減できます。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込みに \(O(N)\)、尺取り法による走査に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 各基地の位置 \(X_i\) と費用 \(C_i\) を格納するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python の input() 関数は低速なため、大量のデータを読み込む際は sys.stdin.read().split() を使用して一括で取得し、リスト化することで実行時間を短縮できます。

• 予算オーバーの基地: もし特定の基地 1 つの費用 \(C_i\) がすでに予算 \(M\) を超えている場合、尺取り法の内部で \(r\) が \(l\) を追い越さないように注意して処理する必要があります。

• インデックスの管理: 尺取り法では「半開区間 \([l, r)\)」として管理すると、要素の追加や削除のロジックがシンプルになります。今回のコードでは \(r\) が「次に含める候補」を指すように実装されています。

  ソースコード

import sys

def solve():
    # 高速な入力読み込みのために、全ての入力を一度に読み込んで分割します。
    # この方法は、Pythonにおいて多くの入力（今回は約4*10^5個の整数）を処理する際に効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 中継基地の数, M: 予算
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各基地の位置 X と稼働費用 C を格納するためのリストを事前に確保します。
    X = [0] * N
    C = [0] * N
    
    # 入力データから各基地の情報をパースします。
    # 基地の情報は位置の昇順で与えられることが保証されています。
    for i in range(N):
        X[i] = int(input_data[2 + 2*i])
        C[i] = int(input_data[3 + 2*i])
        
    max_len = 0
    r = 0
    current_cost = 0
    
    # 尺取り法（Two-pointer approach）を用いて、予算 M 以内で稼働させることができる
    # 連続する基地の区間 [l, r-1] を探索し、その最大長 X[r-1] - X[l] を求めます。
    # ここで l は区間の開始インデックス、 r-1 は終了インデックスです。
    for l in range(N):
        # 現在の合計費用 current_cost に次の基地 r の費用を加えても予算 M を超えない限り、
        # 右側のポインタ r を進めて区間を広げます。
        while r < N and current_cost + C[r] <= M:
            current_cost += C[r]
            r += 1
        
        # r > l の場合、少なくとも1つの基地が予算内で稼働可能です。
        # その区間 [l, r-1] における回線の長さ X[r-1] - X[l] を計算し、最大値を更新します。
        # 基地が1つのみの場合 (r = l + 1)、長さは X[l] - X[l] = 0 となります。
        if r > l:
            length = X[r-1] - X[l]
            if length > max_len:
                max_len = length
            
            # 次の開始位置 l+1 に備えて、現在の基地 l の費用を合計から差し引きます。
            current_cost -= C[l]
        else:
            # もし基地 l 自体の費用が予算 M を超えている場合、区間は空になります。
            # r を l+1 に進め、次のループで l が l+1 になったときに r = l となるようにします。
            r = l + 1
            current_cost = 0
            
    # 求まった最大長を出力します。
    sys.stdout.write(str(max_len) + '\n')

if __name__ == '__main__':
    solve()

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