概要

この問題は、予算 \(K\) 円以内という制約（ナップサック問題の要素）と、隣り合う街路灯を同時に選べないという制約（最大独立集合問題の要素）を組み合わせた最適化問題です。動的計画法（DP）を用いることで、効率的に最大値を求めることができます。

考察

まず、この問題の難しさは \(2\) つの制約が同時に存在することにあります。

1. 費用の制約: 合計費用を \(K\) 以下にする必要がある（典型的なナップサック問題）。
2. 配置の制約: 隣り合う街路灯を同時に選べない。

もし費用の制約がなければ、「\(i\) 番目まで見た時の最大値」を保持する単純な DP で解けます。逆に配置の制約がなければ、通常の \(0/1\) ナップサック問題として解けます。

これらを組み合わせるために、「\(i\) 番目の街路灯を交換したか・していないか」という状態を保持しながら、予算ごとの最大値を更新していくというアプローチをとります。

具体的には、以下の \(2\) つの状態を管理します。 - dp0[j]: \(i\) 番目まで考慮し、合計費用が \(j\) で、\(i\) 番目を交換しない場合の最大削減効果 - dp1[j]: \(i\) 番目まで考慮し、合計費用が \(j\) で、\(i\) 番目を交換する場合の最大削減効果

アルゴリズム

動的計画法（DP）を用いて解きます。

1. DPテーブルの定義

• dp0[j] : 予算 \(j\) を使った時の、\(i\) 番目を「選ばない」状態での最大利益
• dp1[j] : 予算 \(j\) を使った時の、\(i\) 番目を「選ぶ」状態での最大利益

2. 初期状態

• dp0[0] = 0
• それ以外のすべての値は、到達不可能であることを示す非常に小さな値（\(-\infty\)）で初期化します。

3. 遷移（\(i\) 番目の街路灯 \(V_i, W_i\) について）

新しい状態を new_dp0, new_dp1 とすると、次のように更新されます。

• \(i\) 番目を交換しない場合 (new_dp0)
  • \(i-1\) 番目を「交換していても」「交換していなくても」どちらでも構いません。
  • new_dp0[j] = max(dp0[j], dp1[j])
• \(i\) 番目を交換する場合 (new_dp1)
  • 隣り合う街路灯は交換できないため、\(i-1\) 番目は「交換していない」状態からのみ遷移できます。
  • new_dp1[j] = dp0[j - W_i] + V_i （ただし \(j \geq W_i\) のとき）

4. 最終的な答え

すべての街路灯を考慮した後、dp0 と dp1 のすべての要素の中の最大値が答えとなります。

計算量

• 時間計算量: \(O(NK)\)
  • 街路灯の数 \(N\) に対して、予算 \(K\) 分のループ（または配列操作）を繰り返すためです。
  • \(N=200, K=10,000\) のとき、計算回数は約 \(2 \times 10^6\) 回となり、実行時間制限内に十分収まります。
• 空間計算量: \(O(K)\)
  • 直前の状態のみを保持すればよいため、街路灯の数 \(N\) に依存しないメモリ量で実装可能です。

実装のポイント

• 初期化: 削減効果が \(0\) になる可能性もあるため、未到達の状態は 0 ではなく -1 や -10^18 などの十分小さな値で初期化する必要があります。

• Pythonでの高速化: Pythonで \(K\) 回のループを回すと遅くなる場合があります。提供されたコードのように、リストのスライスや map(max, ...) を活用することで、内部的に C 言語で処理され高速に動作します。

• 予算の範囲: new_dp1 を更新する際、予算 \(W_i\) 未満のインデックスにアクセスしないよう注意が必要です。

  ソースコード

import sys

def solve():
    # 競技プログラミングにおいて高速な入力読み込みを行うため、sys.stdin.read().split()を使用します。
    # これにより、すべての入力トークンをリストとして取得できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 街路灯の数, K: 予算の上限
    N = int(input_data[0])
    K = int(input_data[1])
    
    # dp0[j]: i番目までの街路灯を考慮し、合計費用がjで、i番目を「交換しない」場合の最大削減効果
    # dp1[j]: i番目までの街路灯を考慮し、合計費用がjで、i番目を「交換する」場合の最大削減効果
    # 到達不可能な状態を表現するために、十分に小さな負の数（-INF）で初期化します。
    INF = 10**18
    dp0 = [-INF] * (K + 1)
    dp1 = [-INF] * (K + 1)
    
    # 初期状態：0個の街路灯を考慮し、費用0、削減効果0
    dp0[0] = 0
    
    # 各街路灯について順番にDPテーブルを更新します。
    for i in range(N):
        # i番目の街路灯の削減効果 V_i と交換費用 W_i
        v = int(input_data[2 + 2 * i])
        w = int(input_data[3 + 2 * i])
        
        # new_dp0: 今回の街路灯を「交換しない」場合の更新
        # 前の街路灯が「交換された」か「交換されていない」かのどちらの状態からも遷移可能です。
        # Pythonのmap(max, ...)は要素ごとの最大値を高速に計算できます。
        new_dp0 = list(map(max, dp0, dp1))
        
        # new_dp1: 今回の街路灯を「交換する」場合の更新
        # 隣り合う街路灯を同時に交換できないため、前の街路灯が「交換されていない」状態からのみ遷移可能です。
        new_dp1 = [-INF] * (K + 1)
        if w <= K:
            # 予算内の範囲で、前の状態(dp0)に削減効果 v を加算します。
            # リストのスライスとリスト内包表記を用いることで、Pythonでの処理速度を向上させます。
            dp0_prev_part = dp0[:K - w + 1]
            new_dp1[w:] = [x + v for x in dp0_prev_part]
        
        # DPテーブルを更新
        dp0 = new_dp0
        dp1 = new_dp1
        
    # すべての街路灯を考慮した後の、予算内での最大削減効果を求めます。
    # dp0[0]が常に0以上であるため、ansも必ず0以上になります。
    ans = max(max(dp0), max(dp1))
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

---

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