概要

納期付きの仕事をスケジューリングして報酬を最大化する問題。\(K\) 個以上の仕事を完了するとボーナスが加算されるため、仕事の数も追跡する必要がある。

考察

重要な気づき①：納期順ソートの正当性

複数の仕事を選んでスケジュールする際、納期が早い順に処理する（EDF: Earliest Deadline First）のが最適です。直感的には、納期が早い仕事を先に片付けないと、後回しにすると間に合わなくなるためです。これにより、仕事を納期順にソートして順番に「選ぶ/選ばない」を決めるDPに帰着できます。

重要な気づき②：ボーナス条件の扱い

ボーナスは完了した仕事が \(K\) 個以上のときに得られるため、DPの状態として「完了した仕事の数」も追跡する必要があります。ただし、\(K\) 個以上であれば何個でもボーナスは同じ \(B\) なので、仕事数のカウントは \(K\) で打ち切れます（\(K\) 以上はすべて同じ扱い）。

素朴なアプローチの問題

仕事の部分集合を全探索すると \(2^N\) 通りで、\(N=200\) では不可能です。DPを使いますが、状態を「時刻 \(t\)」だけにすると仕事数がわからずボーナス判定ができません。

アルゴリズム

DP定義: \(dp[t][c]\) = 現在までに \(t\) 日分の作業時間を使い、\(c\) 個の仕事を完了したときの報酬の最大値

• \(t\): \(0 \leq t \leq M\)（使った日数。次の仕事は \(t+1\) 日目から開始可能）
• \(c\): \(0 \leq c \leq K\)（完了した仕事数。\(K\) で打ち切り）

手順:

1. 仕事を納期 \(T_i\) の昇順にソートする
2. 初期状態: \(dp[0][0] = 0\)、それ以外は \(-\infty\)
3. 各仕事 \(i\)（ソート後）について、0-1ナップサック的に更新する：
   • 仕事 \(i\) を開始できる条件: 開始日 \(t+1\) として、完了日 \(t+D_i \leq T_i\)、すなわち \(t \leq T_i - D_i\)
   • 遷移: \(dp[t + D_i][\min(c+1, K)] \leftarrow \max(\cdot,\; dp[t][c] + V_i)\)
   • 同じ仕事を複数回使わないよう、\(t\) を大きい方から小さい方へ走査する（0-1ナップサックの定石）
4. 最後に全状態を走査し、\(c \geq K\) なら \(B\) を加算して最大値を求める

具体例: \(M=10\), 仕事A（\(D=3, V=5, T=5\)）, 仕事B（\(D=2, V=3, T=8\)）の場合 - \(dp[0][0]=0\) → 仕事Aを選ぶ → \(dp[3][1]=5\) → 仕事Bを選ぶ → \(dp[5][2]=8\)

計算量

• 時間計算量: \(O(N \cdot M \cdot K)\)
  • 仕事数 \(N\) 回のループ × 時刻 \(M\) × カウント \(K\) の状態更新
  • 最悪 \(200 \times 5000 \times 200 = 2 \times 10^8\)
• 空間計算量: \(O(M \cdot K)\)
  • DP テーブルのサイズ: \((M+1) \times (K+1)\)

実装のポイント

• 0-1ナップサックの逆順走査: 各仕事を高々1回しか使えないため、時刻 \(t\) を大きい方から更新する。これにより同じ仕事を重複して選ぶことを防ぐ。

• カウントの打ち切り: 仕事数 \(c\) を \(K\) で打ち切ることで、状態数を抑える。\(c = K\) は「\(K\) 個以上完了」を意味する。

• 開始可能時刻の上限: \(t \leq T_i - D_i\) かつ \(t \leq M - D_i\)（\(T_i \leq M\) なので前者が支配的だが、配列外アクセス防止のため min(max_t, M - D) とする）。

• 高速入力: Python では sys.stdin.buffer.read() を使って入力を一括読み込みし、速度を確保する。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    jobs = []
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        jobs.append((D, V, T))
    
    # Sort jobs by deadline (greedy scheduling: EDF ordering)
    jobs.sort(key=lambda x: x[2])
    
    # We need to track both total value and number of jobs completed.
    # Since bonus depends on whether count >= K, we need to know the count.
    # 
    # DP approach: dp[j][c] = max total value when current time is j and c jobs completed
    # But c can be up to N=200 and j up to M=5000, so dp table is 5001 * 201 which is ~1M entries.
    # With N=200 jobs, total operations ~ 200 * 5000 * 200 = 200M which might be tight in Python.
    #
    # Optimization: cap c at K since for bonus we only care if c >= K.
    # dp[j][c] for c = 0..K, where c=K means "K or more jobs completed"
    # This gives 5001 * (K+1) entries, and K <= 200, so still up to 1M * 200 = 200M in worst case.
    #
    # Let's try with capping at K.
    
    NEG_INF = -1
    
    # dp[t][c] = max value achievable, having used time up to t, with c jobs done
    # c is capped at K
    cap = K
    
    # Use 1D arrays for efficiency: dp[t][c]
    # dp is (M+1) x (cap+1)
    dp = [[NEG_INF] * (cap + 1) for _ in range(M + 1)]
    dp[0][0] = 0
    
    for job_idx in range(N):
        D, V, T = jobs[job_idx]
        # Process in reverse to avoid using same job twice
        # For each state (t, c), if we schedule this job starting at time t,
        # it finishes at t + D - 1, which must be <= T, i.e., t + D - 1 <= T => t <= T - D + 1
        # Also t + D - 1 <= M => t <= M - D + 1 (but T <= M so T - D + 1 <= M - D + 1)
        max_start = T - D + 1  # latest start time (0-indexed: day t+1 in 1-indexed)
        # Actually let me re-think indexing:
        # dp[t][c] means: the earliest available day is t (0-indexed meaning day t+1 is next available)
        # Wait, let me use: dp[t][c] = max value when all scheduled jobs finish by day t
        # and next job can start on day t+1 (1-indexed).
        # Actually simpler: t = current time used. Next job starts at day t+1.
        # Job starting at day t+1 finishes at day t+D. Need t+D <= T.
        # So t <= T - D.
        
        max_t = T - D  # max value of t such that starting at t+1 finishes at t+D <= T
        if max_t < 0:
            continue
        
        # Iterate t from max_t down to 0, c from cap down to 0
        for t in range(min(max_t, M - D), -1, -1):
            new_t = t + D
            for c in range(cap, -1, -1):
                if dp[t][c] == NEG_INF:
                    continue
                new_c = min(c + 1, cap)
                new_val = dp[t][c] + V
                if new_val > dp[new_t][new_c]:
                    dp[new_t][new_c] = new_val
    
    ans = 0
    for t in range(M + 1):
        for c in range(cap + 1):
            if dp[t][c] == NEG_INF:
                continue
            val = dp[t][c]
            if c >= K:
                val += B
            if val > ans:
                ans = val
    
    print(ans)

solve()

---

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