概要

この問題は、合計の滞在費を \(M\) 以内に抑えつつ、得られる利益を最大化するナップサック問題の変種です。通常のナップサック問題と異なる点は、「選んだ町どうしの間隔が \(K\) 以下でなければならない」という移動距離の制限がある点です。

考察

1. 動的計画法（DP）の定義

「どの町を最後に訪れたか」と「これまでの滞在費の合計」が分かれば、次にどの町に行けるかが決まります。そこで、以下のDPテーブルを定義します。

• dp[i][j]：\(i\) 番目の町を最後に訪れた町として選び、滞在費の合計が \(j\) であるときの利益の最大値

2. 遷移の考え方

町 \(i\) を訪れる場合、その前に訪れた町を \(p\) とすると、問題の条件から \(i - p \leq K\) を満たす必要があります。 つまり、町 \(i\) での利益を \(A_i\)、滞在費を \(B_i\) とすると、遷移式は以下のようになります。

\[dp[i][j + B_i] = \max_{i-K \leq p < i} \{ dp[p][j] \} + A_i\]

また、町 \(i\) を「最初に訪れる町」とする場合は、前の町がないため単純に \(dp[i][B_i] = A_i\) となります。

3. 高速化の工夫

素朴に遷移を計算すると、各 \(i, j\) に対して直近 \(K\) 個の町を探索するため、計算量は \(O(N \times M \times K)\) となります。今回の制約（\(N, M \le 200\)）ではこれでも間に合う可能性がありますが、より効率的に解くためにスライディングウィンドウ・マキシマムの手法を適用できます。

各滞在費 \(j\) ごとに、直近 \(K\) 個の \(dp[p][j]\) の最大値を保持するために「スライディングウィンドウ（deque）」を用いることで、最大値の取得を \(O(1)\) で行うことができます。これにより、全体の計算量を \(O(NM)\) に削減できます。

アルゴリズム

1. DPテーブル dp[N][M+1] を \(-1\)（到達不可能）で初期化します。
2. 各滞在費 \(j \in [0, M]\) に対して、最大値を管理するためのデック（deque）を用意します。
3. 町 \(i = 0\) から \(N-1\) まで順に以下を行います：
   • 各滞在費 \(j\) について、デックの先頭から「現在の町 \(i\) から \(K\) より離れた古い町」のインデックスを削除します。
   • （遷移1） デックの先頭（範囲内の最大値）を使って、dp[i][j + B_i] を更新します。
   • （遷移2） 町 \(i\) を最初の町とする場合（\(dp[i][B_i] = A_i\)）を考慮します。
   • 次の町のために、現在の dp[i][j] をデックに追加します。この際、デック内の値が単調減少になるように維持します。
4. dp テーブル内のすべての値のうち、最大のものが答えです。

計算量

• 時間計算量: \(O(N \times M)\)
  • 町のループ（\(N\)）と滞在費のループ（\(M\)）の二重ループです。デックの操作は各要素につき追加・削除が1回ずつ行われるため、ならし計算量で \(O(1)\) です。
• 空間計算量: \(O(N \times M)\)
  • DPテーブルのサイズが \(N \times (M+1)\) です。

実装のポイント

• 初期化: 利益は \(0\) になることもあるため、未到達の状態は \(-1\) などで区別します。

• デックの管理: deques[j] には「滞在費がちょうど \(j\) のときの、過去 \(K\) 個の町における最大利益」を管理するインデックスを格納します。

• 範囲の判定: 新しい町 \(i\) を処理する前に、デックの先頭にあるインデックス \(p\) が \(i - p \leq K\) を満たしているかを確認します。

  ソースコード

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 町の数, M: 滞在費の総額の上限, K: 馬車が一度に移動できる町の数の上限
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 各町の利益 A_i と滞在費 B_i を取得
    A = []
    B = []
    for i in range(N):
        A.append(int(input_data[3 + 2*i]))
        B.append(int(input_data[4 + 2*i]))
        
    # dp[i][j] は、i 番目の町を最後に訪れ、滞在費の合計が j であるときの最大利益を表す。
    # -1 はその状態が到達不可能であることを示す。
    dp = [[-1] * (M + 1) for _ in range(N)]
    
    # 各滞在費 j について、直近 K 個の町の中での最大利益を効率的に管理するため、スライディングウィンドウ（deque）を使用する。
    # deques[j] は、dp[p][j] (p < i) の最大値を求めるためのインデックスを保持する。
    deques = [deque() for _ in range(M + 1)]
    
    for i in range(N):
        ai = A[i]
        bi = B[i]
        
        # 1. 町 i を、それ以前に訪れた町 p (i-K <= p < i) の次に訪れる場合を考える。
        # 各滞在費 j について、ウィンドウ [i-K, i-1] 内で最大の利益を持つ町 p を deques[j][0] から取得する。
        for j in range(M - bi + 1):
            if deques[j]:
                best_p = deques[j][0]
                # deques[j][0] に入っているインデックス p は、dp[p][j] が最大であることを保証されている。
                if dp[best_p][j] != -1:
                    new_profit = dp[best_p][j] + ai
                    if new_profit > dp[i][j + bi]:
                        dp[i][j + bi] = new_profit
        
        # 2. 町 i を最初に訪れる町とする場合を考える。
        if bi <= M:
            if ai > dp[i][bi]:
                dp[i][bi] = ai
        
        # 3. 次の町 (i+1) 以降の計算のために、現在の dp[i] の結果を deques に追加し、ウィンドウ外のインデックスを削除する。
        for j in range(M + 1):
            # 現在の町 i の結果を deque に追加（単調性を維持）
            if dp[i][j] != -1:
                while deques[j] and dp[deques[j][-1]][j] <= dp[i][j]:
                    deques[j].pop()
                deques[j].append(i)
            
            # 次の町 (i+1) のウィンドウは [i+1-K, i] なので、i+1-K 未満（つまり i-K 以下）のインデックスを削除する。
            if deques[j] and deques[j][0] <= i - K:
                deques[j].popleft()
                
    # 全ての dp テーブルの中から最大の利益を探す。
    ans = 0
    for i in range(N):
        for j in range(M + 1):
            if dp[i][j] > ans:
                ans = dp[i][j]
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

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