概要

街道沿いの町を、移動制限と予算制限を満たしながら訪問し、利益を最大化する動的計画法（DP）の問題です。

考察

問題の整理

• \(N\) 個の町が一列に並んでいる
• 各町には利益 \(A_i\) と滞在費 \(B_i\) がある
• 訪れる町は「隣り合う番号の差が \(K\) 以下」という制限がある
• 滞在費の合計が \(M\) 円以下でなければならない

重要な気づき

1. 訪問順序は必ず西から東（番号の小さい順から大きい順） になります。なぜなら、訪れる町を番号順に並べたときの制約だからです。

2. 「最後に訪れた町」と「使った滞在費」が分かれば、そこからの最適な選択ができます。これは典型的なDPの状態設計です。

3. 町 \(i\) から町 \(j\) へ移動できる条件は：

   • \(i < j\)（東へ進む）
   • \(j - i \leq K\)（移動距離が \(K\) 以下）

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

全ての町の訪問パターンを列挙すると \(2^N\) 通りとなり、\(N = 200\) では到底間に合いません。

DPによる解決

「最後に訪れた町」と「使った滞在費の合計」を状態として持つことで、効率的に解けます。

アルゴリズム

DP の定義

\(dp[i][c]\) = 町 \(i\) を最後に訪れ、滞在費の合計がちょうど \(c\) のときの最大利益

初期値は \(-\infty\)（到達不可能を表す）とします。

初期化

各町 \(i\) を「最初に訪れる町」として選ぶ場合： $\(dp[i][B_i] = A_i \quad (B_i \leq M \text{ のとき})\)$

遷移

町 \(i\) から町 \(j\) へ移動する場合（\(i < j\)、\(j - i \leq K\)）：

\[dp[j][c + B_j] = \max(dp[j][c + B_j], dp[i][c] + A_j)\]

ただし、\(c + B_j \leq M\) のときのみ遷移可能。

具体例

\(N=3, M=5, K=2\) で、町の情報が \((A_1, B_1) = (10, 2), (A_2, B_2) = (20, 3), (A_3, B_3) = (15, 2)\) の場合：

1. 初期化：\(dp[0][2]=10, dp[1][3]=20, dp[2][2]=15\)
2. 町0から町1へ：\(dp[1][2+3]=dp[1][5]=10+20=30\)
3. 町0から町2へ：\(dp[2][2+2]=dp[2][4]=10+15=25\)
4. 町1から町2へ：\(dp[2][3+2]=dp[2][5]=20+15=35\)

答えは \(\max(dp[i][c]) = 35\)

答えの求め方

全ての \(dp[i][c]\) の最大値を取ります。どの町も訪れない場合（利益0）も考慮します。

計算量

• 時間計算量: \(O(N^2 \times M)\)
  • 各町 \(i\) と滞在費 \(c\) の組み合わせが \(O(N \times M)\)
  • 各状態から最大 \(K\) 個（最大 \(N\) 個）の町へ遷移
• 空間計算量: \(O(N \times M)\)
  • DPテーブルのサイズ

実装のポイント

1. 到達不可能状態の管理: INF = float('-inf') を使い、未到達の状態からは遷移しないようにする

2. 遷移の範囲: range(i + 1, min(i + K + 1, N)) で、町 \(i\) から \(K\) 以内の町のみを探索

3. 答えの初期値: どの町も訪れない場合の利益 \(0\) を初期値として、全てのDP値と比較する

4. 滞在費の上限チェック: new_cost <= M の条件を忘れずに確認する

   ソースコード

def solve():
    N, M, K = map(int, input().split())
    towns = []
    for _ in range(N):
        a, b = map(int, input().split())
        towns.append((a, b))
    
    # dp[i][c] = 最後に訪れた町がi、使った滞在費がcのときの最大利益
    # ただし、町iを訪れていない状態も考慮する必要がある
    
    # dp[i][c] = 町iを最後に訪れ、滞在費の合計がちょうどcのときの最大利益
    # -1は到達不可能を表す
    
    INF = float('-inf')
    
    # dp[i][c]: 町iを最後に訪れた町として、滞在費合計がcのときの最大利益
    dp = [[INF] * (M + 1) for _ in range(N)]
    
    # 初期化: 各町を最初の町として訪れる場合
    for i in range(N):
        a, b = towns[i]
        if b <= M:
            dp[i][b] = a
    
    # 遷移: 町iから町jへ移動 (i < j, j - i <= K)
    for i in range(N):
        for c in range(M + 1):
            if dp[i][c] == INF:
                continue
            # 町iから移動できる町j
            for j in range(i + 1, min(i + K + 1, N)):
                a_j, b_j = towns[j]
                new_cost = c + b_j
                if new_cost <= M:
                    dp[j][new_cost] = max(dp[j][new_cost], dp[i][c] + a_j)
    
    # 答え: 全てのdp[i][c]の最大値、または0（どの町も訪れない場合）
    ans = 0
    for i in range(N):
        for c in range(M + 1):
            if dp[i][c] != INF:
                ans = max(ans, dp[i][c])
    
    print(ans)

solve()

---

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