概要

\(N\) 個の部屋を順に訪れ、荷物の積み降ろしの仕事を選択的に引き受けて報酬を最大化する問題です。荷物の個数が常に \(K\) 以下、最終的に \(0\) である必要があり、DPで解きます。

考察

状態の定義

部屋を左から順に処理していくとき、「今何個の荷物を持っているか」が今後の選択に影響する唯一の情報です。そこで次のDPを考えます。

\[dp[j] = \text{現在荷物を } j \text{ 個持っている状態での、これまでの報酬の最大値}\]

初期状態は \(dp[0] = 0\)、それ以外は \(-\infty\)（到達不可能）です。

遷移の考え方

各部屋で「引き受ける」か「断る」の2択があります。断る場合 \(dp[j]\) は変化しません。引き受ける場合は仕事の種類で場合分けします。

荷物を積む仕事（\(T_i = 1\)）の場合： - 荷物 \(j-1\) 個の状態から引き受けると荷物 \(j\) 個になる - \(dp[j] \leftarrow \max(dp[j],\ dp[j-1] + A_i)\)（\(j = 1, 2, \ldots, K\)） - 0-1ナップサック同様、\(j\) を \(K\) から \(1\) へ逆順に処理することで、同じ仕事を二重に適用することを防ぎます

荷物を降ろす仕事（\(T_i = 0\)）の場合： - 荷物 \(j+1\) 個の状態から引き受けると荷物 \(j\) 個になる（\(j \geq 1\)） - 荷物 \(0\) 個の状態でも引き受けられ、荷物は \(0\) のまま報酬だけもらえる - \(j = 0\) の場合：\(dp[0] \leftarrow \max(dp[0],\ dp[1]) + A_i\) - \(j \geq 1\) の場合：\(dp[j] \leftarrow \max(dp[j],\ dp[j+1] + A_i)\) - 遷移が \(j+1 \to j\)（大→小）なので、\(j\) を \(0\) から \(K-1\) へ昇順に処理します

具体例

\(N=3, K=2\), 仕事が \((1,5), (1,3), (0,4)\) の場合：

処理後	\(dp[0]\)	\(dp[1]\)	\(dp[2]\)
初期	0	\(-\infty\)	\(-\infty\)
部屋1（積む,5）	0	5	\(-\infty\)
部屋2（積む,3）	0	5	8
部屋3（降ろす,4）	9	12	8

答えは \(dp[0] = 9\)（部屋1と部屋3を引き受ける）。

アルゴリズム

1. \(dp[0] = 0\)、\(dp[1], \ldots, dp[K] = -\infty\) で初期化
2. 各部屋 \(i = 1, 2, \ldots, N\) について：
   • \(T_i = 1\)（積む）：\(j = K, K-1, \ldots, 1\) の順に \(dp[j] \leftarrow \max(dp[j],\ dp[j-1] + A_i)\)
   • \(T_i = 0\)（降ろす）：
     • \(j = 0\)：\(dp[0] \leftarrow \max(dp[0], dp[1]) + A_i\)（\(dp[0]\) が有効な場合）
     • \(j = 1, 2, \ldots, K-1\)：\(dp[j] \leftarrow \max(dp[j],\ dp[j+1] + A_i)\)
3. 答えは \(\max(dp[0],\ 0)\)

計算量

• 時間計算量: \(O(NK)\)（各部屋で荷物の状態 \(0 \sim K\) を走査）
• 空間計算量: \(O(K)\)（DP配列のサイズ）

制約 \(NK \leq 10^7\) により十分高速に動作します。

実装のポイント

• ループの向きが重要です。積む仕事では逆順（大→小）、降ろす仕事では昇順（小→大）に走査しないと、1回の仕事で複数回遷移してしまうバグが生じます。これは0-1ナップサック問題と同じ考え方です。

• \(T_i = 0\) で \(j = 0\) のとき、荷物がなくても引き受けられる（報酬だけもらえる）特殊なケースを忘れずに処理します。\(dp[0]\) と \(dp[1]\) の両方から遷移可能です。

• \(dp[K]\) は降ろす仕事で \(dp[K+1]\) からの遷移が存在しないため、ループ範囲は \(j = 1, \ldots, K-1\) で十分です。

• 1つも仕事を引き受けない場合（報酬 \(0\)）も有効なので、最終的に \(\max(dp[0], 0)\) を出力します。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    NEG_INF = -(1 << 60)
    dp = [NEG_INF] * (K + 2)  # dp[0..K], extra slot K+1 for convenience
    dp[0] = 0
    
    for i in range(N):
        t = int(data[idx]); idx += 1
        a = int(data[idx]); idx += 1
        
        if t == 1:
            # Pick up cargo: from state j-1 to j
            # Iterate j from K down to 1
            for j in range(K, 0, -1):
                val = dp[j - 1] + a
                if val > dp[j]:
                    dp[j] = val
        else:
            # Drop cargo: from state j+1 to j (j>=1), or from state 0 to 0
            # For j=0: new = max(dp[0], dp[0]+a, dp[1]+a)
            # Since a>=1, dp[0]+a > dp[0] when dp[0] is valid
            # For j>=1: new = max(dp[j], dp[j+1]+a)
            
            # j=0 special case
            candidate0 = dp[0]
            candidate1 = dp[1] if K >= 1 else NEG_INF
            best = candidate0 if candidate0 > candidate1 else candidate1
            if best != NEG_INF:
                val = best + a
                if val > dp[0]:
                    dp[0] = val
            
            # j=1..K-1: accept from j+1
            for j in range(1, K):
                val = dp[j + 1] + a
                if val > dp[j]:
                    dp[j] = val
    
    ans = dp[0] if dp[0] > 0 else 0
    print(ans)

main()

---

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