概要

隣り合う街路灯を同時に選べないという制約の下で、予算内で電気代削減効果を最大化する問題です。これは「隣接制約付きナップサック問題」と呼ばれる動的計画法（DP）の典型問題です。

考察

問題の整理

• \(N\) 個の街路灯から、いくつかを選んでLEDに交換したい
• 制約1: 使う費用の合計が予算 \(K\) 円以下
• 制約2: 隣り合う街路灯（\(i\) 番目と \(i+1\) 番目）を同時に選べない
• 目的: 削減効果 \(V_i\) の合計を最大化

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

全ての選び方を試すと \(2^N\) 通りあり、\(N = 200\) では到底間に合いません。

解決の糸口

通常のナップサック問題では「\(i\) 番目までの品物を見て、重さ \(j\) で得られる最大価値」をDPで求めます。この問題では「隣接制約」があるため、直前の街路灯を選んだかどうかという情報を追加で持つ必要があります。

アルゴリズム

状態の定義

次の2つの配列を使います： - prev_not_selected[j]: 直前の街路灯を選ばなかったとき、予算 \(j\) 円で得られる最大削減効果 - prev_selected[j]: 直前の街路灯を選んだとき、予算 \(j\) 円で得られる最大削減効果

遷移

\(i\) 番目の街路灯（削減効果 \(V_i\)、費用 \(W_i\)）を処理するとき：

1. \(i\) 番目を選ばない場合 - 直前を選んでも選ばなくても良い - curr_not_selected[j] = max(prev_not_selected[j], prev_selected[j])

2. \(i\) 番目を選ぶ場合 - 直前は選んでいない必要がある（隣接制約） - 費用 \(W_i\) を払う必要がある - curr_selected[j] = prev_not_selected[j - W_i] + V_i（ただし \(j \geq W_i\)）

具体例

\(N=3\), \(K=5\) で街路灯が \((V_1, W_1) = (10, 2)\), \((V_2, W_2) = (20, 3)\), \((V_3, W_3) = (15, 2)\) の場合：

• 1番目と2番目を両方選ぶことはできない（隣接）
• 1番目と3番目を選ぶと、費用 \(2+2=4 \leq 5\)、削減効果 \(10+15=25\)
• 2番目だけ選ぶと、費用 \(3\)、削減効果 \(20\)

よって答えは \(25\) となります。

初期化と答え

• 初期状態: 0番目の街路灯を見る前は、何も選んでおらず予算0で削減効果0
• 答え: 全ての街路灯を処理した後、予算 \(0 \sim K\) での最大削減効果

計算量

• 時間計算量: \(O(NK)\)
  • 街路灯 \(N\) 個それぞれについて、予算 \(0 \sim K\) の状態を更新
• 空間計算量: \(O(K)\)
  • 「直前の状態」と「現在の状態」の配列を持つだけで良い

実装のポイント

1. 到達不可能状態の管理: 値として \(-1\)（INF）を使い、その状態からは遷移しないようにする

2. 配列の更新: 前の状態（prev_*）から現在の状態（curr_*）を計算し、処理後に入れ替える

3. 初期状態の設定: prev_not_selected[0] = 0（何も選ばず予算0で削減効果0）から開始

4. 最終的な答え: prev_not_selected と prev_selected の両方から最大値を探す（最後の街路灯を選んでも選ばなくても良いため）

   ソースコード

def solve():
    N, K = map(int, input().split())
    lights = []
    for _ in range(N):
        v, w = map(int, input().split())
        lights.append((v, w))
    
    # dp[i][j] = i番目の街路灯まで考慮し、予算をj円使った時の最大削減効果
    # 状態: 最後の街路灯を選んだかどうかも考慮する必要がある
    # dp[i][j][0] = i番目を選ばない場合の最大削減効果
    # dp[i][j][1] = i番目を選ぶ場合の最大削減効果
    
    # 初期化: -1は到達不可能を表す（削減効果は0以上なので-1で判定）
    INF = -1
    
    # dp[j][0] = 現在の街路灯を選ばない場合、予算jでの最大削減効果
    # dp[j][1] = 現在の街路灯を選ぶ場合、予算jでの最大削減効果
    
    # 初期状態
    prev_not_selected = [0] + [INF] * K  # 何も選ばない状態、予算0で削減効果0
    prev_selected = [INF] * (K + 1)  # まだ何も選んでいない
    
    # 0番目の街路灯から処理
    for i in range(N):
        v, w = lights[i]
        
        curr_not_selected = [INF] * (K + 1)
        curr_selected = [INF] * (K + 1)
        
        for j in range(K + 1):
            # i番目を選ばない場合
            # 前の街路灯を選んでも選ばなくても良い
            if prev_not_selected[j] != INF:
                if curr_not_selected[j] < prev_not_selected[j]:
                    curr_not_selected[j] = prev_not_selected[j]
            if prev_selected[j] != INF:
                if curr_not_selected[j] < prev_selected[j]:
                    curr_not_selected[j] = prev_selected[j]
            
            # i番目を選ぶ場合
            # 前の街路灯は選んでいない必要がある
            if j >= w and prev_not_selected[j - w] != INF:
                new_val = prev_not_selected[j - w] + v
                if curr_selected[j] < new_val:
                    curr_selected[j] = new_val
        
        prev_not_selected = curr_not_selected
        prev_selected = curr_selected
    
    # 最大値を求める
    ans = 0
    for j in range(K + 1):
        if prev_not_selected[j] != INF:
            ans = max(ans, prev_not_selected[j])
        if prev_selected[j] != INF:
            ans = max(ans, prev_selected[j])
    
    print(ans)

solve()

---

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