概要

庭園にある \(N\) 個の飛び石を、最大 \(K\) 回まで「1つ飛ばしで跳ぶ」ことを許容して進むとき、訪れた石のスコアの合計を最大化する問題です。

考察

問題の言い換え

高橋君は飛び石 \(1\) から \(N\) まで移動します。 「1つ飛ばしで跳ぶ」という動作は、ある飛び石を「訪れずにスキップする」ことに対応します。 1つ飛ばしで跳ぶ回数が最大 \(K\) 回であるため、この問題は「訪れない（スキップする）飛び石を最大 \(K\) 個選ぶ」と言い換えることができます。

ただし、移動ルールから以下の制約を満たす必要があります： - 始点（石 \(1\)）と終点（石 \(N\)）は必ず訪れる必要があります。したがって、スキップできるのは石 \(2\) から \(N-1\) のみです。 - 「連続して2つ以上の石をスキップする」ことはできません（1つ飛ばしで跳んだ先から、さらに1つ飛ばしで跳ぶことはできますが、その間に飛ばされる石はそれぞれ独立しています）。つまり、スキップする石は互いに隣接してはなりません。

したがって、問題は以下のようにシンプルに言い換えられます。

\(A_2, \ldots, A_{N-1}\) の中から、互いに隣接しない要素を最大 \(K\) 個選び、それらのスコアの総和を最小化する。 最終的な答えは、（すべての石のスコアの総和）\(-\)（選んだ石のスコアの総和） となる。

なお、スコアが正の石をスキップすると合計スコアが減少してしまうため、スキップする候補として選ぶのはスコアが負の石のみで十分です。

素朴なアプローチ（動的計画法）

動的計画法（DP）を用いると、 \(dp[i][j] = \)（ \(i\) 番目の石まで見て、 \(j\) 回スキップしたときの最小コスト）として解くことができます。 しかし、これでは状態数が \(O(N K)\) となり、 \(N \le 2 \times 10^5, K \le N\) の制約下では、実行時間制限に間に合いません（最悪で \(O(N^2)\) の計算量になります）。

貪欲法と巻き戻し（双方向リスト＋優先度付きキュー）

隣接しない要素を \(K\) 個選んで最小化（または最大化）する問題は、「貪欲法に巻き戻し（後悔）の選択肢を取り入れる」ことで高速に解くことができます。

最もスコアが小さい（負の絶対値が大きい）要素 \(i\) を選ぶことを考えます。 要素 \(i\) を選んだ（スキップした）場合、その両隣の要素 \(l\) と \(r\) は選べなくなります。 しかし、「\(i\) を選ぶ」のが常に最適とは限りません。「\(i\) を選ばずに、両隣の \(l\) と \(r\) の両方を選ぶ」方が、合計の減少幅が大きくなる（よりお得になる）場合があります。

この「後悔」をシミュレートするために、以下の操作を行います： 1. 現在選択可能な中で最も値が小さい要素 \(val[i]\) を選ぶ。 2. その両隣 \(l, r\) を削除する（今後単体で選ばれないようにする）。 3. 要素 \(i\) の値を \(val[l] + val[r] - val[i]\) に更新し、優先度付きキューに戻す。 4. 双方向リストを用いて、要素 \(i\) の両隣を \(left[l]\) と \(right[r]\) に繋ぎ直す。

この更新された値 \(val[i] = val[l] + val[r] - val[i]\) を後から選ぶことは、「最初に選んだ \(val[i]\) をキャンセルして、代わりに \(val[l]\) と \(val[r]\) を選ぶ」ことに相当します。 なぜなら、 $\(\text{（最初に得た利益 } val[i] \text{）} + \text{（新しく得た利益 } val[l] + val[r] - val[i] \text{）} = val[l] + val[r]\)$ となり、正しく選択の巻き戻しが成立するからです。

アルゴリズム

1. すべての石のスコアの総和 total_sum を計算します。
2. 各石の値を保持する配列 val、および左右の隣接関係を表す双方向リスト left, right を用意します。
   • 石 \(1\) と石 \(N\) はスキップできないため、 val[0] と val[N-1] には十分に大きな値（INF）を設定しておきます。
3. 優先度付きキュー（最小ヒープ）に、石 \(2\) から \(N-1\) のインデックスと値のペア (val[i], i) をすべて追加します。
4. 以下の操作を最大 \(K\) 回繰り返します：
   • キューから最小値を持つ要素 \(i\) を取り出す。すでに削除された要素であれば無視して次を取り出す。
   • もし \(val[i] \geq 0\) なら、これ以上スコアを減らせない（スキップしても得しない）ため、ループを終了する。
   • スコアの最小値の累積 S_min に \(val[i]\) を加算する。
   • \(i\) の両隣 \(l = left[i], r = right[i]\) を削除済み（deleted）とする。
   • \(val[i]\) を \(val[l] + val[r] - val[i]\) に更新し、キューに再挿入する。
   • 双方向リストを更新し、 \(i\) の左を \(left[l]\) に、右を \(right[r]\) に繋ぎ直す。
5. 最終的な答えは total_sum - S_min となります。

計算量

• 時間計算量: \(O(N \log N)\) 優先度付きキューへの要素の挿入・削除が最大 \(O(N)\) 回行われます。各操作は \(O(\log N)\) であるため、全体の時間計算量は \(O(N \log N)\) となり、制約時間内に十分間に合います。
• 空間計算量: \(O(N)\) 双方向リスト用の配列や優先度付きキューに格納される要素数は最大でも \(O(N)\) です。

実装のポイント

• 両端の番兵: 石 \(1\) と石 \(N\) はスキップできないため、初期値として INF を設定することで、貪欲法の中で絶対に選ばれないようにしています。

• 削除済みフラグ: 要素が「巻き戻し」によって実質的に削除されたことを示すために deleted 配列を使用します。キューから取り出した要素がすでに削除されている場合は、スキップして次の要素を処理します。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = 1e16;

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);
    long long total_sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        total_sum += A[i];
    }

    if (N <= 2) {
        cout << total_sum << "\n";
        return 0;
    }

    vector<long long> val(N);
    vector<int> left(N), right(N);
    vector<bool> deleted(N, false);

    val[0] = INF;
    val[N - 1] = INF;
    for (int i = 1; i <= N - 2; ++i) {
        val[i] = A[i];
    }

    for (int i = 0; i < N; ++i) {
        left[i] = i - 1;
        right[i] = i + 1;
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= N - 2; ++i) {
        pq.push({val[i], i});
    }

    long long S_min = 0;
    for (int k = 0; k < K; ++k) {
        while (!pq.empty() && deleted[pq.top().second]) {
            pq.pop();
        }
        if (pq.empty()) break;
        auto [v, i] = pq.top();
        pq.pop();
        if (v >= 0) break;

        S_min += v;
        int l = left[i];
        int r = right[i];
        deleted[l] = true;
        deleted[r] = true;

        long long next_val = val[l] + val[r] - val[i];
        if (next_val > INF) next_val = INF;
        val[i] = next_val;

        left[i] = left[l];
        right[i] = right[r];
        if (left[i] >= 0) {
            right[left[i]] = i;
        }
        if (right[i] < N) {
            left[right[i]] = i;
        }
        pq.push({val[i], i});
    }

    cout << total_sum - S_min << "\n";

    return 0;
}

---

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