概要

\(N\) 個の街路灯の中から、予算 \(K\) 円以内でいくつかをLEDに交換し、年間の電気代削減額の合計を最大化する問題。ただし、隣り合う2つの街灯を同時に交換することはできない。

考察

この問題は、ナップサック問題の応用と考えることができます。各街灯には「価値」（削減効果 \(V_i\)）と「重み」（費用 \(W_i\)）があり、予算という容量 \(K\) のナップサックに入れられるように選ぶ必要があります。

しかし単なるナップサックではなく、「隣り合う2つを同時に選んではいけない」という制約があります。これは、動的計画法（DP）を用いる際に、直前の選択を記録しておく必要があることを意味します。

たとえば、以下のような素朴なDPを考えると失敗します： - dp[i][k] := \(i\) 番目まで見て、コストが \(k\) 以下であるような選び方での最大効果
このままでは「\(i-1\) 番目を選んだか？」が分からないので、隣接制約を守れません。

そこで、DPテーブルに「直前に選んだか？」の状態を持たせます： - dp[i][k][last] := \(i\) 番目まで見て、コストが \(k\) 以下で、直前（\(i-1\) 番目）を選んだか（last = 1 or 0）での最大効果

このように状態を持つことで、「\(i-1\) を選んでいたら \(i\) は選べない」という遷移が可能です。

また、空間計算量を抑えるために、現在と1つ前の状態だけ保持するローリングDP（空間削減テク）を使います。

アルゴリズム

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

DPテーブルの定義

• dp[k][last] := 現在のコストが \(k\) 以下であり、直前の街灯を選んだか（last = 1: 選んだ、0: 選んでいない）ときの最大削減効果

初期化

• 最初の街灯（\(i = 0\)）に対して：
  • 選ぶ場合：dp[W[0]][1] = V[0] （予算OKなら）
  • 選ばない場合：dp[k][0] = 0

遷移

\(i = 1\) から \(N - 1\) まで順に更新： - \(i\) 番目を選ばない： - curr_dp[k][0] = max(prev_dp[k][0], prev_dp[k][1]) - \(i\) 番目を選ぶ（ただし \(k \geq W[i]\) かつ prev_dp[k - W[i]][0] からの遷移）： - curr_dp[k][1] = max(curr_dp[k][1], prev_dp[k - W[i]][0] + V[i])

答え

• 最後の状態において、max(dp[k][0], dp[k][1]) の最大値（\(k = 0\)～\(K\)）

計算量

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

※ ローリングDPにより、空間を大幅に節約している。

実装のポイント

• prev_dp と curr_dp の2つだけを使ってDPテーブルを更新することで、空間計算量を削減。
• 「隣接禁止」の条件を満たすために、last という状態を導入して遷移を丁寧に管理する。
• 最後に全コスト範囲で最大値を取ることを忘れない（dp[k][0], dp[k][1] 両方見る）。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    V = [0] * N
    W = [0] * N
    
    for i in range(N):
        V[i] = int(data[2 + 2*i])
        W[i] = int(data[3 + 2*i])
    
    # dp[i][k][last] := i番目まで見て、コストがk以下で、i-1番目を選んだかどうか(last=1:選んだ, 0:選んでない)時の最大効果
    # ただし、last == 1 のとき i-1番目を選んでいるので i番目は選べない。
    # 配列を毎回確保するとメモリが足りるか怪しいので、空間削減したDPを行う。
    
    # dp[k][last] := コストがk以下で、直前を選んだかどうか(last=1:選んだ, 0:選ばない)時の最大効果
    prev_dp = [[0]*2 for _ in range(K+1)]
    
    # 初期状態: 0番目を考える
    # 0番目を選ばない: dp[k][0] = 0
    # 0番目を選ぶ:     dp[w0][1] = v0 (w0 <= K)
    curr_dp = [[0]*2 for _ in range(K+1)]
    if W[0] <= K:
        curr_dp[W[0]][1] = V[0]
    for k in range(K+1):
        curr_dp[k][0] = 0
    
    prev_dp = curr_dp
    
    # i=1 から N-1まで処理
    for i in range(1, N):
        curr_dp = [[0]*2 for _ in range(K+1)]
        w = W[i]
        v = V[i]
        for k in range(K+1):
            # i番目を選ばない場合
            curr_dp[k][0] = max(prev_dp[k][0], prev_dp[k][1])
            
            # i番目を選ぶ場合（予算内かつ前のが選ばれていない）
            if k >= w:
                curr_dp[k][1] = max(curr_dp[k][1], prev_dp[k-w][0] + v)
        
        prev_dp = curr_dp
    
    # 最終的な答えは max(dp[K][0], dp[K][1])
    res = 0
    for k in range(K+1):
        res = max(res, prev_dp[k][0], prev_dp[k][1])
    print(res)

if __name__ == "__main__":
    main()

---

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