概要

連続する \(K\) 個のブロックを何度でも消して、最終的に残るブロックの合計を最大化する問題です。

重要なのは、「どのブロックを残すか」を考えると、消えるブロックの連続区間の長さは必ず \(K\) の倍数になる、という点です。

考察

最終的に残るブロックを固定して考えます。

例えば、残るブロックを 1、消えるブロックを 0 として表すと、最終状態は次のような形になります。

11100011100000011

ここで、消えるブロック 0 の連続区間に注目します。

操作では一度にちょうど \(K\) 個の連続したブロックを消します。
また、残すブロックをまたいで左右のブロックを同時に消すことはできません。

したがって、最終的に消えるブロックの各連続区間の長さは、必ず \(K\) の倍数でなければなりません。

逆に、消えるブロックの各連続区間の長さが \(K\) の倍数なら、その区間を \(K\) 個ずつ消していけばよいので、実現可能です。

つまり、この問題は次のように言い換えられます。

各ブロックについて「残す」か「消す」かを決める。
ただし、消すブロックの連続区間の長さはすべて \(K\) の倍数でなければならない。
残したブロックの合計を最大化する。

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

そこで、左から順に見ていく動的計画法を考えます。

アルゴリズム

\(dp[i]\) を次のように定義します。

左から \(i\) 個目までのブロックを見たとき、条件を満たすように残したブロックの合計の最大値

初期値は、

\[ dp[0] = 0 \]

です。

\(i\) 番目のブロックについて、選択肢は大きく分けて 2 つあります。

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

この場合、\(i-1\) 番目までの最適解に \(A_i\) を足せばよいです。

\[ dp[i] = dp[i-1] + A_i \]

2. 最後の \(K\) 個のブロックを消す

\(i-K+1, i-K+2, \ldots, i\) 番目の \(K\) 個をまとめて消すと考えます。

この場合、残る合計は \(i-K\) 番目までの最適値と同じです。

\[ dp[i] = dp[i-K] \]

したがって、\(i \geq K\) のとき、

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

となります。

一方で、\(i < K\) のときはまだ \(K\) 個まとめて消すことができないので、

\[ dp[i] = dp[i-1] + A_i \]

です。

例えば \(K=2\) のとき、消える連続区間の長さは \(2,4,6,\ldots\) でなければなりません。
長さ \(4\) の連続区間を消す場合も、「最後の \(2\) 個を消す」という遷移を 2 回行うことで表現できます。

最終的な答えは、

\[ dp[N] \]

です。

計算量

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

通常の DP 配列をそのまま持つと \(O(N)\) メモリが必要ですが、遷移に必要なのは \(dp[i-1]\) と \(dp[i-K]\) だけです。

そのため、コードでは長さ \(K\) の配列を使って、\(dp[i-K]\) を取り出せるようにしています。

実装のポイント

prev に直前の値 \(dp[i-1]\) を持たせています。

また、配列 dp は長さ \(K\) の循環配列として使っています。

\(i\) 番目を処理するとき、\(i\) と \(i-K\) は \(K\) で割った余りが同じなので、dp[i % K] に \(dp[i-K]\) が入っています。

コード中では r が現在の \(i \bmod K\) に対応しています。

keep = prev + x
skip = dp[r]
cur = max(keep, skip)

• keep: 現在のブロックを残す場合
• skip: 最後の \(K\) 個を消す場合

ただし、\(i < K\) の間はまだ \(K\) 個を消せないので、keep のみを使います。

また、\(A_i\) の絶対値は最大 \(10^9\)、\(N\) は最大 \(10^6\) なので、合計は \(10^{15}\) 程度になる可能性があります。
Python では整数が任意精度なので問題ありませんが、C++ などでは long long を使う必要があります。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    while data[idx] <= 32:
        idx += 1
    x = 0
    while data[idx] > 32:
        x = x * 10 + (data[idx] - 48)
        idx += 1
    N = x

    while data[idx] <= 32:
        idx += 1
    x = 0
    while data[idx] > 32:
        x = x * 10 + (data[idx] - 48)
        idx += 1
    K = x

    dp = [0] * K
    prev = 0
    r = 0

    for i in range(1, N + 1):
        while data[idx] <= 32:
            idx += 1

        neg = False
        if data[idx] == 45:
            neg = True
            idx += 1

        x = 0
        while idx < ndata and data[idx] > 32:
            x = x * 10 + (data[idx] - 48)
            idx += 1

        if neg:
            x = -x

        r += 1
        if r == K:
            r = 0

        keep = prev + x
        if i >= K:
            skip = dp[r]
            cur = skip if skip > keep else keep
        else:
            cur = keep

        dp[r] = cur
        prev = cur

    print(prev)

if __name__ == "__main__":
    main()

---

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