概要

この問題は、長さ \(N\) の数列から「連続する \(K\) 個の要素を消去する」という操作を繰り返したときに、残った要素の合計値を最大化する問題です。 動的計画法（DP）を適用し、さらに状態の持ち方を工夫することで、時間複雑度 \(O(N)\) で効率的に解くことができます。

---

考察

1. 操作の性質の言い換え

一見すると、要素を消去して「左に詰める」という操作は複雑に見えます。しかし、操作を繰り返した結果として「消去された部分」に着目すると、重要な性質が見えてきます。

消去される要素は、常に1回の操作につき \(K\) 個です。したがって、最終的に消去されたいくつかの区間の長さは、必ず \(K\) の倍数 になります。 逆に、長さが \(K\) の倍数であるような連続する区間は、端から順に \(K\) 個ずつ消去していくことで、元の数列においてどのように並んでいても完全に消し去ることができます。

このことから、問題は以下のようにシンプルに言い換えることができます。

「数列から、互いに重ならない『長さが \(K\) の倍数である区間』をいくつか選び、それらをすべて消去したときの、残った要素の合計の最大値を求める」

2. 素朴な動的計画法（DP）

この言い換えを元に、以下のようなDPを定義します。 - \(dp[i]\) : 数列の最初の \(i\) 個の要素（\(A_1, A_2, \ldots, A_i\)）まで処理したときの、残った要素の合計の最大値

\(dp[i]\) の値は、以下の2つの選択肢のうち大きい方になります。

1. \(i\) 番目の要素を残す場合 \(i\) 番目の要素 \(A_i\) を残すため、その直前までの最大値に \(A_i\) を加えます。 $\(dp[i] = dp[i-1] + A_i\)$

2. \(i\) 番目の要素を「消去する区間の右端」とする場合 ある \(j < i\) が存在して、区間 \([j+1, i]\)（長さ \(i-j\)）を消去します。このとき、長さ \(i-j\) は \(K\) の倍数でなければなりません。 $\(dp[i] = \max_{\substack{0 \le j < i \\ (i-j) \equiv 0 \pmod K}} dp[j]\)\( 条件 \)(i-j) \equiv 0 \pmod K\( は、**\)j \equiv i \pmod K$** と言い換えることができます。

3. 高速化

上記の遷移をそのまま実装すると、各 \(i\) に対して \(j\) の候補が \(O(N/K)\) 個存在するため、全体の計算量が \(O(N^2 / K)\) となり、最悪の場合（\(K=1\) など）に実行時間制限に間に合いません（TLE）。

ここで、条件 \(j \equiv i \pmod K\) に注目します。 \(i\) を \(K\) で割った余りを \(r\) とすると、遷移の候補となる \(dp[j]\) はすべて 「インデックスを \(K\) で割った余りが \(r\) であるもの」 に限られます。

したがって、余り \(r\)（\(0 \le r < K\)）ごとに、これまでに登場した \(dp[j]\) の最大値を記録しておく配列 max_dp[r] を用意します。 $\(max\_dp[r] = \max_{\substack{j < i \\ j \equiv r \pmod K}} dp[j]\)$

これを用いることで、選択肢2の遷移は以下のように \(O(1)\) で計算できるようになります。 $\(dp[i] = max\_dp[i \bmod K]\)$

---

アルゴリズム

1. 配列の初期化:

   • \(dp\) 配列をサイズ \(N+1\) で作成し、初期値を \(-\infty\)（非常に小さな値）にします。ただし、\(dp[0] = 0\) とします。
   • max_dp 配列をサイズ \(K\) で作成し、初期値を \(-\infty\) にします。ただし、max_dp[0] = 0 とします（\(dp[0]\) のインデックス \(0\) は \(0 \bmod K = 0\) であるため）。

2. DPの遷移: \(i = 1\) から \(N\) まで順に以下を行います。

   • 要素を残す遷移: \(val = dp[i-1] + A_i\)
   • 要素を消去する遷移: \(r = i \bmod K\) としたとき、\(val = \max(val, max\_dp[r])\)
   • \(dp[i] = val\) とする。
   • max_dp[r] を \(dp[i]\) を用いて更新する: \(max\_dp[r] = \max(max\_dp[r], dp[i])\)

3. 答えの出力:

   • 最終的な答えは \(dp[N]\) となります。

---

計算量

• 時間計算量: \(O(N)\) \(i\) を \(1\) から \(N\) までループさせ、各ステップでの遷移は \(O(1)\) で行えるため、全体の計算量は \(O(N)\) となり、非常に高速です。
• 空間計算量: \(O(N)\) DPテーブル dp のサイズが \(N+1\)、max_dp のサイズが \(K\) であるため、空間計算量は \(O(N + K) = O(N)\) です。

---

実装のポイント

• 初期値の \(-\infty\): 到達不可能な状態を表すために、十分に小さな値（1e18 など）を \(-\infty\) として使用します。遷移の際にオーバーフローを防ぐため、データ型は long long を使用してください。

• 1-indexed と 0-indexed の対応: コード中では、要素 \(A\) は 0 から N-1 までの 0-indexed で管理されていますが、DPの遷移 \(i\) は 1 から N までの 1-indexed に対応しています。そのため、要素 \(A_i\) を参照する際は A[i-1] となる点に注意してください。

  ソースコード

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

using namespace std;

const long long INF = 1e18;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // dp[i] は A の最初の i 個の要素を処理したときの最大値
    vector<long long> dp(N + 1, -INF);
    // max_dp[r] は、インデックス j % K == r である dp[j] の最大値
    vector<long long> max_dp(K, -INF);

    dp[0] = 0;
    max_dp[0] = 0;

    for (int i = 1; i <= N; ++i) {
        long long val = -INF;
        // i 番目の要素を残す場合
        if (dp[i - 1] != -INF) {
            val = dp[i - 1] + A[i - 1];
        }
        // i 番目の要素を消去する区間の右端とする場合
        int r = i % K;
        if (max_dp[r] != -INF) {
            val = max(val, max_dp[r]);
        }
        dp[i] = val;
        if (dp[i] != -INF) {
            max_dp[r] = max(max_dp[r], dp[i]);
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

---

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