概要

この問題は、長さ \(N\) の数列から「連続する \(K\) 個の要素を消去する」という操作を繰り返したときに、残った要素の総和を最大化する問題です。

一見すると消去する位置の組み合わせが膨大に見えますが、「残せる要素の元の位置（インデックス）」に強力な制約があることに注目すると、動的計画法（DP）を用いて時間計算量 \(O(N)\)、空間計算量 \(O(K)\) で効率的に解くことができます。

考察

1. キーとなる観察：残せる要素の条件

操作「連続する \(K\) 個のブロックを消去する」を繰り返したとき、最終的に残るブロックの元のインデックス（1-based）を左から順に \(i_1, i_2, \ldots, i_m\) とします。

このとき、消去される部分は以下の3つのパターンに分類されます。 - 先頭部分: \(i_1\) の手前にある \(i_1 - 1\) 個の要素 - 要素の間: \(i_j\) と \(i_{j+1}\) の間にある \(i_{j+1} - i_j - 1\) 個の要素 - 末尾部分: \(i_m\) の後ろにある \(N - i_m\) 個の要素

1回の操作で消去される要素数はちょうど \(K\) 個なので、消去された各区間の要素数はすべて \(K\) の倍数でなければなりません。したがって、以下の条件が成り立ちます。

1. 先頭： \(i_1 - 1 \equiv 0 \pmod K \implies i_1 \equiv 1 \pmod K\)
2. 隙間： \(i_{j+1} - i_j - 1 \equiv 0 \pmod K \implies i_{j+1} \equiv i_j + 1 \pmod K\)
3. 末尾： \(N - i_m \equiv 0 \pmod K \implies i_m \equiv N \pmod K\)

この関係を順に適用していくと、残す要素の元のインデックスについて以下の非常に綺麗な性質が得られます。 - 1番目に残す要素： \(i_1 \equiv 1 \pmod K\) - 2番目に残す要素： \(i_2 \equiv 2 \pmod K\) - \(j\) 番目に残す要素： \(i_j \equiv j \pmod K\) - 最後に残す要素（\(m\) 番目）： \(i_m \equiv m \equiv N \pmod K\)

つまり、「\(j\) 番目に残す要素の元のインデックス \(i_j\) は、 \(i_j \equiv j \pmod K\) を満たさなければならない」 ということです。

具体例 (\(K=3\) の場合)

残す要素の元のインデックスは、以下のように決まります。 - 1番目に残す要素は、 \(1, 4, 7, \ldots\) 番目のいずれか - 2番目に残す要素は、 \(2, 5, 8, \ldots\) 番目のいずれか - 3番目に残す要素は、 \(3, 6, 9, \ldots\) 番目のいずれか

2. 動的計画法（DP）への帰着

配列を左から順に走査しながら、各要素 \(A[i]\) を「残す」か「消去する」かを決定していきます。 現在のインデックスを \(i\)、その \(K\) で割った余りを \(r = i \pmod K\) とします。

インデックス \(i\) の要素 \(A[i]\) に注目したとき、選択肢は以下の2つです。

1. \(A[i]\) を「残す」場合 \(A[i]\) は \(j \equiv r \pmod K\) 番目の残る要素になります。その直前に残した要素（\(j-1\) 番目）は、余りが \(r-1\) の位置にあるはずです。 したがって、「直前の要素まで処理して、残した個数の余りが \(r-1\) である状態の最大値」に \(A[i]\) を加えた値になります。

2. \(A[i]\) を「消去する」場合 \(A[i]\) を消去するということは、最後に残した要素がもっと手前のインデックス \(i'\) （ただし \(i' \equiv r \pmod K\)）にあり、そこから現在までの要素（\(i - i'\) 個、これは \(K\) の倍数）をすべて消去することを意味します。 このときの最大値は、過去に記録された「余りが \(r\) の状態の最大値」そのものです。

この2つの選択肢のうち、値が大きい方を採用していくことで最適な状態を更新できます。

アルゴリズム

DPテーブルの定義

• max_dp[r]: これまでに処理した要素の中で、残した個数の余りが \(r\) である状態の最大値。
• dp_prev: 直前の要素まで処理したときの最大値。

遷移

各要素 \(a = A[i]\) （\(r = i \pmod K\)）について、以下のように更新します。

1. \(a\) を残す場合と消去する場合の最大値を取る： $\(val = \max(\text{dp\_prev} + a, \text{max\_dp}[r])\)$
2. 次のステップのために dp_prev を val に更新する。
3. max_dp[r] を val で更新（より大きい場合のみ上書き）する。

初期値

• max_dp のすべての要素を \(-\infty\) で初期化します。ただし、何も残さない状態（個数0、余り0）の初期値として max_dp[0] = 0 とします。
• dp_prev = 0

計算量

• 時間計算量: \(O(N)\) 配列 \(A\) を \(1\) 回走査するだけであり、各ステップの処理は \(O(1)\) です。 \(N = 10^6\) でも 0.1 秒未満で高速に動作します。
• 空間計算量: \(O(K)\) 保持する DP テーブルのサイズは \(K\) のみであるため、メモリをほとんど消費しません。

実装のポイント

• 剰余演算の最適化: ループ内で毎回 i % K を計算する代わりに、変数 r をインクリメントし、 r == K になったら 0 に戻すことで、剰余演算を避けて実行速度を高速化しています。

• 十分小さな値での初期化: 配列の要素には負の値も含まれるため、 max_dp の初期値は -10**18 などの十分に小さな値（\(-\infty\)）にする必要があります。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]

    INF = 10**18
    max_dp = [-INF] * K
    max_dp[0] = 0

    dp_prev = 0
    r = 0
    for a in A:
        val = dp_prev + a
        r += 1
        if r == K:
            r = 0
        if max_dp[r] > val:
            val = max_dp[r]
        dp_prev = val
        if val > max_dp[r]:
            max_dp[r] = val

    print(dp_prev)


if __name__ == "__main__":
    solve()

---

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