概要

納期と所要時間がある複数の仕事から、得られる報酬が最大となるように仕事の選択とスケジュールを決定する問題です。完了した仕事の数が \(K\) 個以上の場合に一度だけ追加のボーナス \(B\) が得られるという特徴があります。

考察

1. 仕事の処理順序の決定（EDFルールの適用）

締め切り（納期 \(T_i\)）が存在するスケジューリング問題では、「納期が早い仕事から順に処理する」（Earliest Deadline First: EDF）という貪欲な順序付けが最適であることが知られています。 ある仕事の集合を納期を守ってスケジュールできるならば、それらを納期が早い順に並べ替えても必ず納期を守ることができます。したがって、あらかじめ仕事を納期 \(T_i\) の昇順にソートしておくことで、仕事を処理する順番を固定でき、問題は「各仕事を順番に見ていき、それを行うか行わないか」を決める動的計画法（DP）に帰着できます。

2. 動的計画法（DP）の設計

ボーナス \(B\) は「完了した仕事の個数が \(K\) 以上」のときに得られます。そのため、単に「経過日数」だけをDPの状態に持つと、これまでにいくつの仕事をこなしたかが分からず、ボーナスを適用すべきか判断できません。 そこで、DPの状態に「これまでに完了した仕事の個数」も含める必要があります。

• DPテーブルの定義 \(dp[c][j] :=\) これまでに選んだ仕事の数が \(c\) 個で、消費した合計日数が \(j\) 日であるときの、得られる報酬の最大値。

3. 遷移の条件

仕事 \(i\)（必要な日数 \(D_i\)、納期 \(T_i\)、報酬 \(V_i\)）をこなす場合を考えます。 仕事 \(i\) を行う直前の経過日数を \(j\) としたとき、この仕事を納期内に完了させるためには、完了時の日数が納期以下、すなわち \(j + D_i \le T_i\) である必要があります。 これを変形すると \(j \le T_i - D_i\) となります。

したがって、仕事 \(i\) を行うことができるのは、これまでの経過日数 \(j\) が \(\min(T_i - D_i, M)\) 以下である場合に限られます。このとき、以下のように遷移します。 $\(dp[c+1][j + D_i] = \max(dp[c+1][j + D_i], dp[c][j] + V_i)\)$

アルゴリズム

1. ソート: すべての仕事を納期 \(T_i\) の昇順にソートします。
2. 初期化: DPテーブル dp[c][j]（\(0 \le c \le N, 0 \le j \le M\)）をすべて \(-1\)（到達不可能）で初期化し、初期状態として dp[0][0] = 0 とします。
3. DPの遷移: ソートされた各仕事 \(i = 0, 1, \dots, N-1\) について、以下の順でループを回してDPテーブルを更新します。
   • 仕事数 \(c\) を \(i\) から \(0\) まで逆順にループします。
   • 経過日数 \(j\) を \(\min(T_i - D_i, M)\) から \(0\) まで逆順にループします。
   • dp[c][j] != -1 かつ \(j + D_i \le M\) であれば、上記の遷移式に従って dp[c+1][j + D_i] を更新します。
4. 答えの計算: すべての状態 \(dp[c][j]\) を探索します。もし \(dp[c][j] \neq -1\) であれば：
   • \(c \ge K\) のとき、スコアは \(dp[c][j] + B\) となります。
   • \(c < K\) のとき、スコアは \(dp[c][j]\) となります。 これらのスコアの最大値が求める答えとなります。

計算量

• 時間計算量: \(O(N \log N + N^2 M)\)

  • 仕事のソートに \(O(N \log N)\) かかります。
  • DPの遷移において、仕事のループ（\(N\) 回）、仕事数 \(c\) のループ（最大 \(N\) 回）、経過日数 \(j\) のループ（最大 \(M\) 回）が入れ子になっているため、遷移全体の計算量は \(O(N^2 M)\) となります。
  • 制約 \(N \le 200, M \le 5000\) のとき、最悪でもループ回数は約 \(2 \times 10^8\) 回であり、実行時間制限（通常 2.0 秒）内に十分高速に動作します。

• 空間計算量: \(O(NM)\)

  • DPテーブルのサイズは \((N+1) \times (M+1)\) です。
  • \(205 \times 5005 \times 8 \text{ bytes} \approx 8.2 \text{ MB}\) であり、メモリ制限に対して非常に余裕があります。

実装のポイント

• ループの逆順化: 同じ仕事を1日に何度も引き受けることはできないため、1つのDPテーブルをインプレースで更新する際には、仕事数 \(c\) と経過日数 \(j\) のループを必ず大きい方から小さい方へ（逆順に）回す必要があります。これにより、仕事 \(i\) の情報を更新する際に、同じ仕事 \(i\) を適用した後の状態からさらに重ねて適用してしまう重複カウントを防ぐことができます。

• オーバーフローの防止: 報酬 \(V_i\) やボーナス \(B\) は最大で \(10^9\) であり、それらの総和は \(2 \times 10^{11}\) を超える可能性があります。32ビット整数型（int）ではオーバーフローするため、C++では long long 型を使用する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Job {
    int d;
    long long v;
    int t;
    bool operator<(const Job& other) const {
        return t < other.t;
    }
};

long long dp[205][5005];

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    long long b;
    if (!(cin >> n >> m >> k >> b)) return 0;

    vector<Job> jobs(n);
    for (int i = 0; i < n; ++i) {
        cin >> jobs[i].d >> jobs[i].v >> jobs[i].t;
    }

    // Sort jobs by their deadlines
    sort(jobs.begin(), jobs.end());

    // Initialize DP table
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;

    // DP transitions
    for (int i = 0; i < n; ++i) {
        int d = jobs[i].d;
        long long v = jobs[i].v;
        int t = jobs[i].t;
        for (int c = i; c >= 0; --c) {
            int limit = min(t - d, m);
            for (int j = limit; j >= 0; --j) {
                if (dp[c][j] != -1) {
                    if (j + d <= m) {
                        dp[c + 1][j + d] = max(dp[c + 1][j + d], dp[c][j] + v);
                    }
                }
            }
        }
    }

    // Find the maximum reward
    long long ans = 0;
    for (int c = 0; c <= n; ++c) {
        for (int j = 0; j <= m; ++j) {
            if (dp[c][j] != -1) {
                long long score = dp[c][j];
                if (c >= k) {
                    score += b;
                }
                ans = max(ans, score);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

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