概要

連続する \(K\) 個のブロックを何度でも消せるとき、最終的に残るブロックの合計値の最大値を求めます。

重要なのは、「残すブロック」と「消すブロック」を左から順に見ると、消す部分は長さ \(K\) のかたまりとして扱える、という点です。

考察

最終的に残るブロックの位置を考えます。

残るブロックは、消されることがないので、削除操作によってそれをまたいで左右のブロックがつながることはありません。

したがって、残るブロック同士の間にある消されるブロック列や、最初の残るブロックより左側・最後の残るブロックより右側の消されるブロック列は、それぞれ独立に消す必要があります。

長さ \(K\) の連続ブロックを消す操作しかできないので、それらの消される区間の長さは \(K\) の倍数でなければなりません。

逆に、消す区間の長さが \(K\) の倍数なら、そこを長さ \(K\) ずつに分けて消せます。

つまり、元の列を左から見て、

• 残すブロック 1 個
• 消す連続 \(K\) 個のブロック

のどちらかに分解する問題だと考えられます。

例えば \(K=2\) のとき、長さ \(2\) の区間は消せますが、離れた 2 個のブロックを直接まとめて消すことはできません。

そのため、「残すブロックを自由に選ぶ」だけでは正しくありません。

素朴に操作列を全探索すると、消す区間の選び方が非常に多く、\(N \leq 10^6\) では到底間に合いません。

そこで、左から順に DP します。

アルゴリズム

\(dp[i]\) を「先頭から \(i\) 個目までのブロックについて、合法に残す・消すを決めたときの最大合計」とします。

\(i\) 個目のブロックを考えると、最後の状態は次の 2 通りです。

1. \(i\) 個目のブロックを残す

この場合、先頭から \(i-1\) 個目まではすでに合法に処理されていればよいです。

得点は

\(dp[i-1] + A_i\)

です。

2. 最後の \(K\) 個をまとめて消す

\(i-K+1\) 個目から \(i\) 個目までの \(K\) 個を消すと考えます。

この場合、先頭から \(i-K\) 個目までが合法に処理されていればよいです。

得点は

\(dp[i-K]\)

です。

したがって、遷移は次のようになります。

\(dp[i] = \max(dp[i-1] + A_i,\ dp[i-K])\)

ただし、\(i<K\) のときは \(dp[i-K]\) は存在しないので使えません。

初期値は

\(dp[0] = 0\)

です。

実装では \(dp[i]\) は \(dp[i-1]\) と \(dp[i-K]\) だけを参照するため、配列全体を持つ必要はありません。

\(K\) 個分だけ持つローリング DP にできます。

コード中では、

vector<long long> dp(K, NEG);
dp[0] = 0;

として、添字を \(K\) で割った余りで管理しています。

処理中に、

• dp[i % K] には更新前の \(dp[i-K]\)
• dp[(i-1) % K] には \(dp[i-1]\)

が入っています。

そのため、次のように更新できます。

dp[to] = max(dp[to], dp[from] + a);

これは

\(dp[i] = \max(dp[i-K], dp[i-1] + A_i)\)

に対応しています。

最終的な答えは、先頭から \(N\) 個すべてを処理した値なので、

dp[N % K]

です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(K)\)

実装のポイント

到達不可能な状態を表すために、十分小さい値 NEG を使っています。

\(A_i\) は最大で \(10^9\)、\(N\) は最大で \(10^6\) なので、合計値は最大でおよそ \(10^{15}\) になります。

そのため、int ではなく long long を使う必要があります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    const long long NEG = -(1LL << 62);
    vector<long long> dp(K, NEG);
    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
        long long a;
        cin >> a;

        int from = (i - 1) % K;
        int to = i % K;

        if (dp[from] != NEG) {
            dp[to] = max(dp[to], dp[from] + a);
        }
    }

    cout << dp[N % K] << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。