概要

一列に並んだ \(N\) 個の区画から予算 \(W\) 以内で区画を選び、各区画の美しさの合計に加え、連続して選んだ区画のボーナス（長さ \(L \geq 2\) の連続区間から \(L \times B\)）を最大化する問題です。ナップサック問題に「連続選択ボーナス」の要素を加えた変種です。

考察

重要な気づき

1. 通常のナップサック問題との違い: 各区画を独立に選ぶだけでなく、「隣接する区画を連続して選ぶ」ことでボーナスが発生するため、直前の区画を選んだかどうかの情報が必要です。

2. ボーナスの増分に注目: 連続区間の長さ \(L\) に応じたボーナス \(L \times B\) を最後にまとめて計算しようとすると、連続区間の長さを状態として持つ必要があり、状態数が爆発します。しかし、ボーナスの増分に着目すると：

   • 長さ \(1 \to 2\) に伸びるとき：ボーナスが \(0 \to 2B\) なので \(+2B\)
   • 長さ \(L \to L+1\)（\(L \geq 2\)）に伸びるとき：ボーナスが \(LB \to (L+1)B\) なので \(+B\)

つまり、連続区間の正確な長さを覚えなくても、「長さが \(1\) か \(2\) 以上か」だけ区別すれば増分を正しく計算できます。

1. 3状態で管理: 直前の区画の状態を以下の3つに分ければ十分です：
   • 状態0: 直前の区画を選んでいない（または最初の区画）
   • 状態1: 直前の区画を選んでおり、現在の連続区間の長さが \(1\)
   • 状態2: 直前の区画を選んでおり、現在の連続区間の長さが \(2\) 以上

アルゴリズム

\(dp[w][s]\) = 費用 \(w\) を使い、直前の状態が \(s\)（\(s \in \{0, 1, 2\}\)）であるときの最大価値

各区画 \(i\) について、以下の遷移を行います：

具体例: 区画 \(\{2,3,4\}\) を選ぶ場合（\(B=5\)） - 区画2を選ぶ：状態0→状態1、\(+D_2\) - 区画3を選ぶ：状態1→状態2、\(+D_3 + 2 \times 5 = D_3 + 10\) - 区画4を選ぶ：状態2→状態2、\(+D_4 + 5\)

合計ボーナス = \(10 + 5 = 15 = 3 \times 5\) ✓

最終的な答えは、全区画処理後の全状態・全費用における最大値です。

計算量

• 時間計算量: \(O(N \times W)\)（各区画について費用 \(0 \sim W\) の各状態を定数回更新）
• 空間計算量: \(O(W)\)（各状態について長さ \(W+1\) の配列を3本保持）

実装のポイント

• 配列を3本（dp0, dp1, dp2）に分離: 2次元配列のインデックスアクセスを避け、高速化しています。

• NEG_INF = -1 による到達不能状態の管理: 値が常に非負であるため、\(-1\) を「到達不能」の印として安全に使えます。

• 遷移の際の w + ci <= W チェック: 予算超過を防ぐための条件分岐です。

• 最終回答で状態1, 2も参照: 最後の区画が連続区間の途中で終わる場合もあるため、全状態の最大値を取ります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    D = []
    C = []
    for i in range(N):
        d = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        D.append(d)
        C.append(c)
    
    # State: dp[i][w][s] where:
    # i = current item index (0..N-1)
    # w = weight used so far (0..W)
    # s = state regarding the last item:
    #   s=0: last item was NOT selected (or no item yet)
    #   s=1: last item WAS selected and is part of a run of length 1
    #   s=2: last item WAS selected and is part of a run of length >= 2
    #
    # When we don't select item i:
    #   If previous state was s=0: new state is 0, no change in value
    #   If previous state was s=1: run of length 1 ends, bonus = 0, new state = 0
    #   If previous state was s=2: run of length >= 2 ends, but bonus was already added incrementally, new state = 0
    #
    # When we select item i:
    #   If previous state was s=0: start new run of length 1, gain D[i], new state = 1
    #   If previous state was s=1: extend run from 1 to 2, gain D[i] + 2*B (because L goes from 1 to 2, bonus goes from 0 to 2B, delta = 2B), new state = 2
    #   If previous state was s=2: extend run from L>=2 to L+1, gain D[i] + B (bonus increases by B), new state = 2
    
    # dp[w][s] = max value achievable considering items 0..i-1 with weight w and state s
    
    NEG_INF = -1
    
    # Initialize: before processing any item, state is (w=0, s=0) with value 0
    # dp[w][s]: use flat arrays for speed
    # s=0,1,2
    
    dp0 = [NEG_INF] * (W + 1)  # state 0
    dp1 = [NEG_INF] * (W + 1)  # state 1
    dp2 = [NEG_INF] * (W + 1)  # state 2
    
    dp0[0] = 0
    
    for i in range(N):
        di = D[i]
        ci = C[i]
        
        new_dp0 = [NEG_INF] * (W + 1)
        new_dp1 = [NEG_INF] * (W + 1)
        new_dp2 = [NEG_INF] * (W + 1)
        
        for w in range(W + 1):
            # From state 0
            v0 = dp0[w]
            if v0 != NEG_INF:
                # Don't select i
                if v0 > new_dp0[w]:
                    new_dp0[w] = v0
                # Select i: new run of length 1
                if w + ci <= W:
                    val = v0 + di
                    if val > new_dp1[w + ci]:
                        new_dp1[w + ci] = val
            
            # From state 1
            v1 = dp1[w]
            if v1 != NEG_INF:
                # Don't select i: run of length 1 ends, bonus 0
                if v1 > new_dp0[w]:
                    new_dp0[w] = v1
                # Select i: extend run 1->2, gain D[i] + 2B
                if w + ci <= W:
                    val = v1 + di + 2 * B
                    if val > new_dp2[w + ci]:
                        new_dp2[w + ci] = val
            
            # From state 2
            v2 = dp2[w]
            if v2 != NEG_INF:
                # Don't select i: run of length >=2 ends
                if v2 > new_dp0[w]:
                    new_dp0[w] = v2
                # Select i: extend run, gain D[i] + B
                if w + ci <= W:
                    val = v2 + di + B
                    if val > new_dp2[w + ci]:
                        new_dp2[w + ci] = val
        
        dp0 = new_dp0
        dp1 = new_dp1
        dp2 = new_dp2
    
    ans = 0
    for w in range(W + 1):
        if dp0[w] > ans:
            ans = dp0[w]
        if dp1[w] > ans:
            ans = dp1[w]
        if dp2[w] > ans:
            ans = dp2[w]
    
    print(ans)

main()

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