概要

「町番号の差が常に \(K\) 以下になるようにいくつかの町を訪れ、滞在費合計が \(M\) 以下の範囲で利益合計を最大化する」問題を、動的計画法（DP）で解きます。

考察

訪れる町を小さい順に並べた列 \(p_1<p_2<\dots<p_m\) は、常に \(p_{t+1}-p_t\le K\) を満たす必要があります。これは「町 \(j\) から町 \(i\) に移動できるのは \(1\le i-j\le K\) のときだけ」という制約なので、

• 町を頂点
• \(j\to i\)（\(i-j\le K\)）を辺

とみなすと、「どこから始めてもよい DAG 上のパス」を選ぶ問題になります。さらに各町には - 利益 \(A_i\) - コスト（滞在費） \(B_i\)

があり、合計コストが \(M\) 以下という“予算制約付きの最長（最大利益）パス”です。

素朴に「訪れる町の部分集合」を全探索すると \(2^N\) で不可能です。また「予算 \(M\) があるナップサック」だけを考えて町を選ぶと、町番号差 \(\le K\) の制約（訪問順の制約）を扱えず WA になります。

ここで重要なのは、最後に訪れた町が分かれば、次に行ける町は「高々 \(K\) 個前まで」に限られる点です。よって「最後の町」と「使える予算」を状態にした DP が自然に立ちます。

アルゴリズム

DP を次で定義します。

• \(dp[i][c]\)：予算上限が \(c\) 円のとき、最後に訪れる町が \(i\) であるような訪問列の利益最大値（存在しなければ \(-\infty\)）

ここで \(c\) は「ちょうど \(c\) 円使う」ではなく「\(c\) 円まで使ってよい（\(\le c\)）」という意味にします。問題の制約が「合計 \(\le M\)」なので、この解釈が合っています。

遷移

町 \(i\) を最後にするには、直前の町 \(j\) は [ \max(1,i-K)\le j \le i-1 ] の範囲に限られます。

町 \(i\) の滞在費を \(B_i\) とすると、予算 \(c\) のとき \(i\) に使えるのは \(B_i\) 円なので、直前までに使える予算上限は \(r=c-B_i\) です。よって [ dp[i][c] = Ai + \max\Bigl(0,\ \max{j\in[i-K,i-1]} dp[j][c-B_i]\Bigr) ] となります。

• \(\max(\cdot,0)\) は「町 \(i\) から新しく始める（直前がない）」ことを表します。どの町も訪れないケースもあるので、答えの初期値は \(0\) です。
• 実装では \(dp\) の初期値を十分小さい負の値（INF_NEG）にし、best = 0 から始めて「開始」も同時に扱っています。

最後に、答えは [ \max_{i=1..N,\ c=0..M} dp[i][c] ] ですが、コードでは計算しながら ans を更新しています（訪れない場合の \(0\) も考慮済み）。

計算量

• 時間計算量: \(O(N \cdot M \cdot K)\)
  （各 \(i\) と各 \(c\) について、最大 \(K\) 個の直前候補 \(j\) を見る）
• 空間計算量: \(O(N \cdot M)\)
  （\(dp\) テーブル）

制約 \(N\le200, M\le200\) なので最大でも \(200\cdot200\cdot200=8\times10^6\) 程度で十分間に合います。

実装のポイント

• 到達不能状態は非常に小さい値（INF_NEG）で埋めておくと、max を取りやすいです。

• 「町 \(i\) から開始できる」ことを best = 0 で表現しています（直前の町を選ばない選択肢）。

• 直前候補の範囲は left = max(1, i-K) のように端を丸めます。

• 利益 \(A_i\) は \(10^9\) と大きいので、INF_NEG は十分小さく（例えば -10**30）してオーバーフロー/比較ミスを避けます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i], B[i] = map(int, input().split())

    INF_NEG = -10**30
    dp = [[INF_NEG] * (M + 1) for _ in range(N + 1)]
    ans = 0

    for i in range(1, N + 1):
        bi = B[i]
        ai = A[i]
        left = max(1, i - K)
        for c in range(bi, M + 1):
            r = c - bi
            best = 0  # start at i
            for j in range(left, i):
                v = dp[j][r]
                if v > best:
                    best = v
            val = best + ai
            dp[i][c] = val
            if val > ans:
                ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

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