概要

\(N\) 個の部屋を順に訪れ、荷物を「積む」か「降ろす」仕事を引き受けることで得られる報酬の合計を最大化する問題です。ただし、「持ち運べる荷物は最大 \(K\) 個まで」「最後は必ず荷物を \(0\) 個にする」という条件を満たす必要があります。

考察

この問題は、現在の「部屋の番号」と「持っている荷物の数」によって次の行動が決まるため、動的計画法 (DP) を用いて解くことができます。

1. 状態の定義

各部屋を訪れた時点での状態を次のように定義します。 - dp[i][j] ： \(i\) 番目の部屋まで訪れ、持っている荷物の数が \(j\) 個であるときの報酬の最大値

2. 遷移のルール

部屋 \(i\) での仕事の種類 \(T_i\) と報酬 \(A_i\) に応じて、以下のように遷移します。

荷物を積む仕事 (\(T_i = 1\)) の場合

• 引き受ける: 荷物が \(j-1\) 個から \(j\) 個に増えます。 dp[i][j] = dp[i-1][j-1] + A_i
• 断る: 荷物の数は \(j\) 個のまま変わりません。 dp[i][j] = dp[i-1][j]
• これらを組み合わせて、dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + A_i) となります。

荷物を降ろす仕事 (\(T_i = 0\)) の場合

• 引き受ける:
  • もともと荷物が \(j+1\) 個あれば、降ろして \(j\) 個になります。
  • もともと荷物が \(0\) 個の場合、降ろしても \(0\) 個のままです（\(j=0\) のときのみ）。 dp[i][j] = dp[i-1][j+1] + A_i （\(j=0\) のときは dp[i][0] = max(dp[i-1][0] + A_i, dp[i-1][1] + A_i)）
• 断る: 荷物の数は \(j\) 個のまま変わりません。 dp[i][j] = dp[i-1][j]
• これらを組み合わせて、dp[i][j] = max(dp[i-1][j], dp[i-1][j+1] + A_i) となります。

3. 条件による範囲の絞り込み

• 荷物の上限: 常に \(0 \leq j \leq K\) である必要があります。
• 最後の条件: 最終的に荷物を \(0\) 個にする必要があるため、部屋 \(i\) にいる時点で、残りの部屋数 \((N-i)\) よりも多くの荷物を持っていると、どう頑張っても \(0\) 個に戻せません。つまり、常に \(j \leq N-i\) である必要があります。

アルゴリズム

1次元配列 dp[j] を用意し、部屋 \(1\) から \(N\) まで順番に更新していきます。

1. 初期化: dp[0] = 0、それ以外を非常に小さな値（\(-\infty\)）にする。
2. 各部屋 \(i\) について:
   • 現在の部屋で持ちうる荷物の最大数 M_curr = min(K, i, N - i) を計算する。
   • \(T_i = 1\) のとき:
     • j を M_curr から \(1\) まで逆順にループし、dp[j] = max(dp[j], dp[j-1] + A_i) と更新する。
   • \(T_i = 0\) のとき:
     • j を \(0\) から M_curr までループし、dp[j] = max(dp[j], dp[j+1] + A_i) と更新する。
3. 答え: 最終的な dp[0] が答えとなります。

※ \(T_i = 1\) で逆順にループするのは、同じ部屋の仕事を一度の更新で複数回引き受けてしまう（\(j-1 \to j \to j+1\) と増えてしまう）のを防ぐためです。

計算量

• 時間計算量: \(O(NK)\)
  • 部屋の数 \(N\) に対して、荷物の数 \(K\) 分のループを回します。
  • 制約より \(NK \leq 10^7\) であるため、Pythonでも効率的に実装すれば制限時間内に間に合います。
• 空間計算量: \(O(K)\)
  • 1次元の DP テーブルのみを保持するため、非常に省メモリです。

実装のポイント

• 高速な入出力: \(N\) や \(K\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

• 到達不能な状態: dp の初期値を -10^18 のような十分小さな値に設定し、計算中に負の無限大が報酬で相殺されないように注意します。

• 範囲の最適化: N - i < j となる状態を -INF でリセットすることで、最終的に荷物を \(0\) 個にできないルートを正しく除外しています。

  ソースコード

import sys

def solve():
    # Fast I/O: Read all input at once and split into strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Parse N and K from the first two elements
    N = int(input_data[0])
    K = int(input_data[1])
    
    # dp[j] stores the maximum reward with exactly j packages.
    # Initialize with a very small number to represent unreachable states.
    INF = 10**18
    dp = [-INF] * (K + 1)
    dp[0] = 0
    
    # M_prev tracks the maximum possible number of packages in the previous step.
    M_prev = 0
    
    # Iterate through each room
    idx = 2
    for i in range(1, N + 1):
        T = int(input_data[idx])
        A = int(input_data[idx+1])
        idx += 2
        
        # M_curr is the maximum number of packages possible at step i.
        # It is constrained by K, the current step i, and the remaining steps N-i.
        M_curr = i
        if K < M_curr: M_curr = K
        if N - i < M_curr: M_curr = N - i
        
        if T == 1:
            # Load a package: dp[j] = max(dp[j], dp[j-1] + A)
            # We iterate backwards to use the values from the previous state (i-1).
            for j in range(M_curr, 0, -1):
                # j-1 is guaranteed to be <= M_prev because M_curr <= M_prev + 1.
                prev_val = dp[j-1]
                if prev_val > -INF // 2:
                    v = prev_val + A
                    if v > dp[j]:
                        dp[j] = v
        else:
            # Unload a package:
            # If j > 0, accept T=0 to go from j packages to j-1 packages.
            # If j = 0, accept T=0 to stay at 0 packages.
            
            # Update state for 0 packages:
            # new_dp[0] = max(dp[0] + A, dp[1] + A, dp[0])
            # Since A >= 1, this simplifies to max(dp[0], dp[1]) + A.
            v0 = dp[0]
            if M_prev >= 1:
                v1 = dp[1]
                if v1 > v0:
                    v0 = v1
            
            if v0 > -INF // 2:
                dp[0] = v0 + A
            
            # Update state for j > 0 packages:
            # new_dp[j] = max(dp[j], dp[j+1] + A)
            for j in range(1, M_curr + 1):
                if j + 1 <= M_prev:
                    v_next = dp[j+1]
                    if v_next > -INF // 2:
                        v = v_next + A
                        if v > dp[j]:
                            dp[j] = v
        
        # Clean up: Any state j > M_curr is now impossible due to N-i constraint.
        # Since M_curr decreases by at most 1, we only need to reset the previous boundary.
        if M_prev > M_curr:
            dp[M_prev] = -INF
            
        M_prev = M_curr
        
    # The answer is the maximum reward with 0 packages remaining at the end.
    # Because declining all jobs is always an option, the result is at least 0.
    print(max(0, dp[0]))

if __name__ == '__main__':
    solve()

---

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