概要

予算 \(M\) 万円以内で連続する基地を稼働させ、敷設できる光ファイバー回線の長さを最大化する問題です。尺取り法を用いて効率的に解くことができます。

考察

問題の言い換え

この問題は「連続する部分配列を選び、コストの総和が \(M\) 以下という制約のもとで、\(X_r - X_l\) を最大化する」という問題に帰着できます。

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

すべての区間 \([l, r]\) を全探索すると、区間の選び方が \(O(N^2)\) 通りあり、各区間のコスト計算に \(O(N)\) かかると、全体で \(O(N^3)\) となります。\(N \leq 2 \times 10^5\) ではTLE（時間超過）になります。

累積和を使えばコスト計算を \(O(1)\) にできますが、それでも \(O(N^2)\) で、まだ間に合いません。

尺取り法が使える理由

この問題には以下の性質があります： - 単調性: 区間を広げるとコストは増加し、区間を狭めるとコストは減少する - 連続区間: 選ぶ基地は連続している必要がある

この性質により、右端 \(r\) を固定したとき、コストが \(M\) 以下となる最小の左端 \(l\) は一意に決まり、\(r\) が増加すると \(l\) も単調に増加（または不変）します。これは尺取り法の適用条件を満たしています。

アルゴリズム

尺取り法（Two Pointers）を使って解きます。

1. 左端 left = 0、現在のコスト current_cost = 0 で初期化
2. 右端 right を \(0\) から \(N-1\) まで順に動かす
3. 各 right について：
   • C[right] を current_cost に加算
   • current_cost > M の間、C[left] を引いて left を右に進める
   • 有効な区間なら、長さ X[right] - X[left] を計算し、最大値を更新
4. 最大値を出力

具体例

\(N = 4, M = 10\) で、各基地が以下の場合を考えます： - 基地1: 位置 \(0\), コスト \(3\) - 基地2: 位置 \(5\), コスト \(4\) - 基地3: 位置 \(8\), コスト \(5\) - 基地4: 位置 \(15\), コスト \(6\)

right	追加後のコスト	left の移動	有効区間	長さ
0	3	なし	[0,0]	0
1	7	なし	[0,1]	5
2	12 → 9	left: 0→1	[1,2]	3
3	15 → 11 → 6	left: 1→2→3	[3,3]	0

この例では、区間 \([0, 1]\) を選んだときの長さ \(5\) が最大となります。

計算量

• 時間計算量: \(O(N)\)
  • right は \(0\) から \(N-1\) まで \(N\) 回進む
  • left も全体を通して最大 \(N\) 回しか進まない
  • よって合計 \(O(N)\)
• 空間計算量: \(O(N)\)
  • 位置配列 \(X\) とコスト配列 \(C\) を保持

実装のポイント

• オーバーフロー対策: \(M\) や \(C_i\) が最大 \(10^{14}\) や \(10^9\) と大きいため、コストの総和が大きくなる可能性があります。Pythonでは整数オーバーフローの心配はありませんが、他言語では64bit整数型を使う必要があります。

• \(l = r\) の場合: 1つの基地のみ稼働する場合、長さは \(0\) です。コードでは X[right] - X[left] を計算するだけで自然に \(0\) になります。

• 有効区間の確認: left <= right かつ current_cost <= M のときのみ長さを計算します。予算内に収まる基地が1つもない場合は、最大長さ \(0\) が出力されます。

  ソースコード

def solve():
    N, M = map(int, input().split())
    X = []
    C = []
    for _ in range(N):
        x, c = map(int, input().split())
        X.append(x)
        C.append(c)
    
    # 尺取り法で解く
    # 連続する区間[l, r]を選び、コストの総和がM以下で、X[r] - X[l]を最大化する
    
    max_length = 0
    current_cost = 0
    left = 0
    
    for right in range(N):
        # right番目の基地を追加
        current_cost += C[right]
        
        # コストがMを超えている間、左端を縮める
        while current_cost > M and left <= right:
            current_cost -= C[left]
            left += 1
        
        # 現在の区間が有効（コストがM以下）なら長さを計算
        if left <= right and current_cost <= M:
            length = X[right] - X[left]
            max_length = max(max_length, length)
    
    print(max_length)

solve()

---

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