概要

横一列に並んだ \(N\) 本の花を切り詰め、任意の連続する \(K\) 本の花の高さの最大値と最小値の差を \(D\) 以下にしつつ、最終的な花の高さの合計を最大化する問題です。

考察

この問題の条件「どの連続する \(K\) 本の花を見ても、最大値と最小値の差が \(D\) 以下」というのは、言い換えると「距離が \(K-1\) 以下の任意の2本の花の高さの差が \(D\) 以下」と同義です。

花の高さは元の高さ \(H_i\) を超えることはできません。したがって、各花の高さの上限を決定していくことを考えます。初期状態では、各花 \(i\) の高さの上限を \(dp[i] = H_i\) とします。

距離が \(K-1\) 以下の2本の花 \(i, j\) について、\(dp[i]\) と \(dp[j]\) の差が \(D\) を超えている場合、高い方の上限を下げて調整する必要があります。具体的には、低い方の上限に \(D\) を足したものが、高い方の上限の候補となります。

全ての花についてこの調整を行うためには、片方の方向（例えば左から右）へ伝播させるだけでは不十分です。右側の花が低いことで、左側の花の上限が下がることもあるためです。そこで、左から右への1パスと、右から左への1パスの計2回の走査を行います。

例えば左から右へ走査する際、花 \(i\) の高さの上限は、左側 \(K-1\) 個の範囲内にある花の \(dp\) 値の最小値に \(D\) を足したもの、という条件で更新します。すなわち \(dp[i] = \min(dp[i], \min(dp[i-K+1], \dots, dp[i-1]) + D)\) とします。右から左へも同様に更新します。

この2パスを行うことで、互いに距離 \(K-1\) 以内にある花の高さの差がすべて \(D\) 以下になる上限が求まります。これらの上限の合計が、花を切り詰めずに残せる最大の高さの合計となります。

アルゴリズム

左から右へ、および右から左への走査において、直近 \(K-1\) 個の \(dp\) 値の最小値を効率的に求めるためにスライド最小値（Sliding Window Minimum）アルゴリズムを使用します。

スライド最小値は、双方向キュー（deque）を用いて実装します。 - キューには要素のインデックスを格納します。 - キューの先頭は、常に現在の区間内での最小値のインデックスです。 - 新しい要素を追加する際、キューの末尾にある要素の \(dp\) 値が追加する要素の \(dp\) 値以上であれば、それらをキューから削除します（単調増加になるように保つ）。 - 区間から外れた（距離が \(K-1\) を超えた）インデックスがキューの先頭にあれば、それを削除します。

これにより、各走査で区間の最小値を \(O(1)\) で取得しながら全体を \(O(N)\) で処理できます。

計算量

• 時間計算量: \(O(N)\) 各要素はdequeに対して高々1回追加され、1回削除されるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\) \(dp\) 配列とdequeのサイズに比例します。

実装のポイント

• \(K = 1\) のときは「連続する1本の花を見ても」という条件になり、最大値と最小値が同じになるため差は常に0となり \(D\) 以下を満たします。したがって、花を一切切らずに合計をそのまま出力します。

• 左から右への走査では、インデックス \(i\) において \(i - (K-1)\) 未満の要素をキューから除外します。右から左への走査では、インデックス \(i\) において \(i + (K-1)\) を超える要素をキューから除外します。

• \(dp[i]\) の更新は、元の上限 \(H_i\) と最小値 \(+ D\) を比較して小さい方を取ることで行います（dp[i] = min(dp[i], dp[dq.front()] + D)）。

  ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    long long D;
    cin >> N >> K >> D;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    if (K == 1) {
        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            ans += H[i];
        }
        cout << ans << "\n";
        return 0;
    }
    
    int L = K - 1;
    vector<long long> dp(N);
    for (int i = 0; i < N; ++i) {
        dp[i] = H[i];
    }
    
    // Left to right pass
    deque<int> dq;
    for (int i = 0; i < N; ++i) {
        if (!dq.empty()) {
            dp[i] = min(dp[i], dp[dq.front()] + D);
        }
        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (!dq.empty() && dq.front() <= i - L) {
            dq.pop_front();
        }
    }
    
    // Right to left pass
    dq.clear();
    for (int i = N - 1; i >= 0; --i) {
        if (!dq.empty()) {
            dp[i] = min(dp[i], dp[dq.front()] + D);
        }
        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (!dq.empty() && dq.front() >= i + L) {
            dq.pop_front();
        }
    }
    
    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += dp[i];
    }
    
    cout << ans << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。