概要

複数の仕事から条件を満たすように仕事を選び、得られる報酬の合計を最大化する問題です。納期が早い順に仕事をソートし、「完了した仕事の数」と「経過日数」を状態に持つ動的計画法（DP）を用いて解きます。

考察

仕事の選び方と順番を両方考える必要があるように見えますが、スケジューリング問題における重要な鉄則があります。それは「納期がある仕事は、納期が早い順に行うのが最適である」ということです。 直感的に考えても、納期が迫っている仕事を後回しにするメリットはありません。納期が早い順に仕事の候補を並べ替えることで、仕事を行う「順番」について悩む必要がなくなり、「その仕事を選ぶか・選ばないか」だけを考えればよくなります。

順番を固定できれば、これは「ナップサック問題」によく似た動的計画法（DP）で解くことができます。 ただし、今回は「完了した仕事が \(K\) 個以上ならボーナス \(B\) がもらえる」という特別なルールがあります。そのため、DPで管理する状態として「現在の経過日数」だけでなく、「これまで完了した仕事の数」も持っておく必要があります。

ボーナスは \(K\) 個以上であれば何個でも同じなので、完了した仕事の数は「 \(0, 1, 2, \dots, K\)（ \(K\) 個以上）」の \(K+1\) 通りだけ管理すれば十分です。

アルゴリズム

1. 事前の準備（ソート） 与えられた \(N\) 個の仕事を、納期 \(T_i\) の昇順（早い順）にソートします。

2. DPテーブルの定義 \(dp[c][d]\) を「完了した仕事数が \(c\) 個、経過日数が \(d\) 日のときの最大報酬」と定義します。

   • \(c\) は \(0\) から \(K\) まで（ \(K\) は「 \(K\) 個以上」を意味します）
   • \(d\) は \(0\) から \(M\) まで
   • 初期状態は \(dp[0][0] = 0\) とし、それ以外は到達不可能として十分に小さな値（ \(-\infty\) ）を入れておきます。

3. DPの遷移 ソートした仕事を順番に見ていき、各仕事（日数 \(D\)、報酬 \(V\)、納期 \(T\)）についてDPテーブルを更新します。 現在の状態が \(dp[c][d]\) のとき、この仕事を選ぶと次のような状態になります。

   • 完了した仕事数: \(\min(c + 1, K)\)
   • 経過日数: \(d + D\)
   • 報酬: \(dp[c][d] + V\)

ただし、仕事を選ぶためには納期に間に合うことが絶対条件です。つまり、 \(d + D \leq T\) を満たす場合のみ遷移できます。 条件を満たす場合、 \(dp[\min(c + 1, K)][d + D]\) を、元の値と新しい報酬の大きい方で更新します。

1. 答えの計算 すべての仕事を見終わった後、DPテーブルの中から最大値を探します。
   • \(c < K\) の場合は、 \(dp[c][d]\) がそのまま最終的な報酬です。
   • \(c = K\) の場合は、ボーナス条件を満たしているため、 \(dp[K][d] + B\) が最終的な報酬になります。 これらのうち、最も大きいものが答えとなります。

計算量

• 時間計算量: \(O(N M K)\)
  • 仕事の数 \(N\) 、完了仕事数の状態 \(K\) 、経過日数 \(M\) の3重ループとなります。最大で \(200 \times 200 \times 5000 = 2 \times 10^8\) 回程度の計算量になりますが、到達不可能な状態をスキップする工夫などにより、実行時間制限内に十分に間に合います。
• 空間計算量: \(O(M K)\)
  • \(K \times M\) の2次元配列を保持するためのメモリが必要です。最大でも \(200 \times 5000 = 10^6\) 要素程度なので、メモリ制限に対して非常に余裕があります。

実装のポイント

• 1つの仕事を複数回選ばないための工夫 0-1ナップサック問題の1次元配列での実装と同様に、完了仕事数 \(c\) のループを 大きい方から降順（ \(K-1\) から \(0\) へ） に回す必要があります。昇順に回してしまうと、同じ仕事を2回以上選んでしまうバグが発生します。

• 状態 \(K\) の特別扱い 完了仕事数がすでに \(K\) 個以上の状態（ \(c = K\) ）に新しい仕事を追加する場合、遷移先も同じ \(c = K\) になります。そのため、正解コードでは \(c = K\) の更新を独立したブロックで行っています。

• Python特有の高速化 Pythonで単純な for ループを使って \(O(N M K)\) を実装すると、実行時間超過（TLE）になる恐れがあります。正解コードでは、到達可能な最大日数を max_d という配列で管理して無駄な計算を省きつつ、リストのスライスと zip を活用して一括で配列を更新することで、大幅な高速化を実現しています。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    B = int(data[3])
    
    jobs = []
    idx = 4
    for _ in range(N):
        jobs.append((int(data[idx]), int(data[idx+1]), int(data[idx+2])))
        idx += 3
        
    # 納期が早い順にソート（区間スケジューリングの基本）
    jobs.sort(key=lambda x: x[2])
    
    MIN_INF = -10**18
    # dp[c][d] : 完了した仕事数が c 個（ただし K 個以上は K として扱う）、経過日数が d 日のときの最大報酬
    dp = [[MIN_INF] * (M + 1) for _ in range(K + 1)]
    dp[0][0] = 0
    
    # 各完了仕事数 c において、到達可能な最大日数を管理して無駄な計算を省く
    max_d = [-1] * (K + 1)
    max_d[0] = 0
    
    for D, V, T in jobs:
        limit = T - D
        if limit < 0:
            continue
            
        dp_K = dp[K]
        max_d_K = max_d[K]
        
        # 完了仕事数がすでに K 個以上の状態への仕事の追加
        if max_d_K != -1:
            end = limit if limit < max_d_K else max_d_K
            if end >= 0:
                dp_K[D : end + D + 1] = [
                    s + V if s + V > t else t
                    for t, s in zip(dp_K[D : end + D + 1], dp_K[: end + 1])
                ]
                if end + D > max_d[K]:
                    max_d[K] = end + D
                    
        # 完了仕事数が K 個未満の状態からの遷移
        for c in range(K - 1, -1, -1):
            max_d_c = max_d[c]
            if max_d_c != -1:
                end = limit if limit < max_d_c else max_d_c
                if end >= 0:
                    dp_c1 = dp[c + 1]
                    dp_c = dp[c]
                    dp_c1[D : end + D + 1] = [
                        s + V if s + V > t else t
                        for t, s in zip(dp_c1[D : end + D + 1], dp_c[: end + 1])
                    ]
                    if end + D > max_d[c + 1]:
                        max_d[c + 1] = end + D
                        
    ans = 0
    
    # ボーナス条件を満たさない場合の最大報酬
    for c in range(K):
        for val in dp[c]:
            if val > ans:
                ans = val
                
    # ボーナス条件を満たす場合の最大報酬
    for val in dp[K]:
        if val != MIN_INF:
            if val + B > ans:
                ans = val + B
                
    print(ans)

if __name__ == '__main__':
    solve()

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