概要

\(N\) 日間の中から最大 \(K\) 日を選び、各選択の間隔を \(D+1\) 日以上空けるという制約のもとで、得られる給料の合計を最大化する問題です。動的計画法（DP）と累積最大値の管理（尺取り法）を用いることで、効率的に解くことができます。

考察

1. 問題の整理

アルバイトをする日を \(p\) 日目、その次のアルバイトを \(q\) 日目とすると、問題の条件から以下を満たす必要があります。 - \(q \ge p + D + 1\) （\(p\) 日目に働いた後、\(D\) 日間休養が必要なため） - 選ぶ日数は合計で \(1\) 日以上 \(K\) 日以下（\(A_i \ge 1\) であるため、働けるなら少なくとも \(1\) 日は働いた方が得です）

2. 素朴なアプローチとその課題

「\(j\) 日間アルバイトをし、最後に働いたのが \(i\) 日目であるときの給料の最大値」を状態とする動的計画法を考えます。 これを \(\text{dp}[j][i]\) と置くと、直前に働いた日 \(p\) に対する遷移は次のようになります。

\[ \text{dp}[j][i] = \max_{1 \le p \le i - D - 1} (\text{dp}[j-1][p]) + A_i \]

この遷移を素直に計算すると、 - 働いた日数 \(j\): \(1 \le j \le K\)（\(O(K)\) 通り） - 最後に働いた日 \(i\): \(1 \le i \le N\)（\(O(N)\) 通り） - 直前に働いた日 \(p\): \(1 \le p \le i - D - 1\)（\(O(N)\) 通り）

全体で \(O(K \times N^2)\) の計算量がかかります。\(N, K \le 5000\) であるため、計算回数が最大で \(5000^3 \approx 1.25 \times 10^{11}\) となり、実行時間制限に間に合わず TLE（実行時間制限超過）となります。

3. 高速化の工夫

\(i\) を \(1\) から \(N\) へと増やしていくとき、遷移元として選べる \(p\) の範囲の上限である \(i - D - 1\) も単調に増加します。 つまり、毎回 \(p\) を \(1\) からループして最大値を探し直す必要はなく、これまでに確認した \(\text{dp}[j-1][p]\) の最大値を保持しながらポインタを進めることで、各 \(i\) に対する最大値の取得を \(O(1)\) で行えます。

これにより、各 \(j\) に対する計算を \(O(N)\) で行えるようになり、全体の時間計算量を \(O(NK)\) に削減できます。

アルゴリズム

1. 初期化:
   • \(j = 1\)（1日だけ働く場合）について、各 \(i\) 日目に働いたときの給料は \(A_i\) です。
   • prev_dp[i] = A[i] とし、答えの最大値 ans もこれで初期化します。
2. DPテーブルの更新:
   • 働く日数 \(j\) を \(2\) から \(K\) まで順にループします。
   • 直前までの最大値を保持する変数 max_val = -1 と、遷移可能な日を管理するポインタ ptr = 1 を用意します。
   • 現在の日 \(i\) を \(1\) から \(N\) まで進めながら、以下を行います：
     1. ptr <= i - D - 1 を満たす間、max_val = max(max_val, prev_dp[ptr]) で更新し、ptr を進める。
     2. max_val != -1（有効な遷移元が存在する）なら、curr_dp[i] = max_val + A[i] とする。
     3. ans = max(ans, curr_dp[i]) で答えを更新する。
   • もし一度も更新が行われなかった場合（制約上、これ以上日数を増やして働くことができない場合）、それ以降の \(j\) を調べる必要はないためループを打ち切ります。
   • prev_dp を curr_dp で置き換えて次の \(j\) に進みます。
3. 出力:
   • 最終的な ans を出力します。

計算量

• 時間計算量: \(O(N \cdot K)\)
  • 外側のループが最大 \(K\) 回回ります。
  • 内側のループでは、\(i\) が \(1\) から \(N\) まで進む間にポインタ ptr も高々 \(N\) までしか進まないため、\(1\) 回の外側ループあたり \(O(N)\) で処理できます。
  • よって全体の計算量は \(O(N \cdot K) \le 5000 \times 5000 = 2.5 \times 10^7\) となり、実行時間制限（通常2秒）に十分間に合います。
• 空間計算量: \(O(N)\)
  • \(j-1\) 日目の状態（prev_dp）と \(j\) 日目の状態（curr_dp）のみを保持する「ローリング配列」の手法を用いているため、配列のサイズは \(O(N)\) で済みます。

実装のポイント

• オーバーフローへの対策: 給料の最大値は \(5000 \times 10^9 = 5 \times 10^{12}\) に達するため、32bit整数型（int）の範囲を超えてしまいます。DPテーブルや答えを格納する変数には必ず 64bit整数型（C++では long long）を使用してください。

• 到達不能状態の扱い: その日数でその日に働くことが不可能な状態を -1 などの番兵で表し、不正な遷移（働けない日からの遷移）が起きないように判定します。

  ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, d;
    if (!(cin >> n >> k >> d)) return 0;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<long long> prev_dp(n + 1, -1);
    long long ans = 0;

    for (int i = 1; i <= n; ++i) {
        prev_dp[i] = a[i];
        ans = max(ans, prev_dp[i]);
    }

    vector<long long> curr_dp(n + 1, -1);

    for (int j = 2; j <= k; ++j) {
        long long max_val = -1;
        int ptr = 1;
        bool any_valid = false;

        for (int i = 1; i <= n; ++i) {
            curr_dp[i] = -1;
            while (ptr <= i - d - 1) {
                if (prev_dp[ptr] != -1) {
                    max_val = max(max_val, prev_dp[ptr]);
                }
                ptr++;
            }
            if (max_val != -1) {
                curr_dp[i] = max_val + a[i];
                ans = max(ans, curr_dp[i]);
                any_valid = true;
            }
        }

        if (!any_valid) {
            break;
        }

        prev_dp = curr_dp;
    }

    cout << ans << "\n";

    return 0;
}

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