概要

東西に並ぶ \(N\) 個の町から、移動制限と予算制限を考慮して利益を最大化する町の選び方を求めます。

考察

この問題では、町の番号が連続していなくてもよいものの、選ぶ町の番号を昇順に並べたときに隣接する番号の差が \(K\) 以下でなければなりません。これは、移動できる範囲が限られていることを意味しています。

例えば、\(K=2\) のとき、町 \(1 \to 3\) への移動は可能ですが、\(1 \to 4\) は不可能です。

また、各町には利益 \(A_i\) と滞在費 \(B_i\) があり、滞在費の合計が \(M\) 円以下という制約のもとで、利益の合計を最大化したいです。

素朴な方法としては、すべての町の部分集合を考え、制約を満たすものの中で利益が最大のものを選ぶことが考えられますが、\(N\) が最大 \(200\) なので、これは計算量的に無理があります（\(2^{200}\) は非常に大きい）。

そこで、「最後に訪れた町」と「そこまでのコスト」に基づいた動的計画法（DP）を用いるのが効果的です。

アルゴリズム

この問題では以下のようなDPテーブルを定義します：

\[ \text{dp}[i][m] := i\text{ 番目の町を最後に選んだ、コストが } m \text{ 以下での最大利益} \]

初期状態では、各町 \(i\) に対して、その町だけを選んだ場合（最初の町）を設定します： - \(\text{dp}[i][B_i] = A_i\) （ただし \(B_i \leq M\)）

次に、各町 \(i\) に対して、次に移動可能な町 \(j\)（つまり \(i < j \leq \min(i + K, N - 1)\)）に対して遷移を行います。

具体的には、現在のコスト \(m\) と利益 \(\text{dp}[i][m]\) から、次の町 \(j\) を訪れる場合の新しいコストと利益を計算し、より良い値があれば更新します：

\[ \text{new\_cost} = m + B_j,\quad \text{new\_profit} = \text{dp}[i][m] + A_j \]

そして、\(\text{new\_cost} \leq M\) かつ \(\text{dp}[j][\text{new\_cost}] < \text{new\_profit}\) なら更新：

\[ \text{dp}[j][\text{new\_cost}] = \text{new\_profit} \]

最終的には、すべての \(\text{dp}[i][m]\) の中で最大の利益を答えとします。

計算量

• 時間計算量: \(O(N \cdot K \cdot M)\)
• 空間計算量: \(O(N \cdot M)\)

\(N, M, K\) が最大でも \(200\) なので、最大で約 \(8 \times 10^6\) 程度の計算となり、十分高速です。

実装のポイント

• DPテーブルは事前に \(-1\) で初期化し、「到達できない状態」を表現する。
• 各町を「最初の町」として初期化する際に、\(B_i \leq M\) のチェックを忘れずに。
• 更新時には、コストオーバーにならないように注意（\(\text{new\_cost} \leq M\)）。
• 最後に全テーブルを走査して最大利益を得ること。

ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    A = [0] * N
    B = [0] * N
    
    for i in range(N):
        A[i] = int(data[3 + 2*i])
        B[i] = int(data[4 + 2*i])
    
    # dp[i][m] := i番目の町を最後に選んだ、コストがm以下での最大利益
    # 初期化: -1 で初期化し、到達不可能を示す
    dp = [[-1] * (M + 1) for _ in range(N)]
    
    # 初期状態：各町を最初に選ぶ場合
    for i in range(N):
        if B[i] <= M:
            dp[i][B[i]] = A[i]
    
    # DP更新
    for i in range(N):
        for j in range(i + 1, min(i + K + 1, N)):
            cost_next = B[j]
            profit_next = A[j]
            for m in range(M - cost_next + 1):
                if dp[i][m] != -1:
                    new_cost = m + cost_next
                    new_profit = dp[i][m] + profit_next
                    if new_cost <= M:
                        if dp[j][new_cost] < new_profit:
                            dp[j][new_cost] = new_profit
    
    # 最大利益を探す
    max_profit = 0
    for i in range(N):
        for m in range(M + 1):
            if dp[i][m] > max_profit:
                max_profit = dp[i][m]
    
    print(max_profit)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。