概要

各花の高さを下げることだけができる状況で、どの連続する \(K\) 本でも高さの最大値と最小値の差が \(D\) 以下になるようにしつつ、最終的な高さの合計を最大化します。

重要なのは、長さ \(K\) の区間条件を「距離が \(K-1\) 以下の任意の2本の高さ差が \(D\) 以下」という条件に言い換えることです。

考察

\(L = K - 1\) とおきます。

連続する \(K\) 本の中に含まれる任意の2本の位置の差は高々 \(K-1 = L\) です。
逆に、位置の差が \(L\) 以下である2本は、必ずどこかの長さ \(K\) の区間に一緒に含まれます。

したがって、条件は次のように言い換えられます。

• すべての \(|i-j| \leq L\) について、\(|H'_i - H'_j| \leq D\)

つまり、距離が \(L\) 以下の花どうしは、高さの差が \(D\) 以下でなければなりません。

---

ある花 \(j\) の高さは最大でも \(H_j\) です。
もし \(|i-j| \leq L\) なら、花 \(i\) の高さは花 \(j\) より \(D\) 以上高くできないので、

\(H'_i \leq H_j + D\)

です。

さらに、距離が直接届かなくても、制約は伝播します。

例えば \(K=3\) なら \(L=2\) なので、2つ先までは直接差が \(D\) 以下です。
位置 \(j\) から位置 \(i\) まで、最大 \(L\) 個ずつ進むとすると、1回進むごとに高さの上限は \(D\) ずつ増えます。

つまり、花 \(j\) から花 \(i\) への最小ステップ数を \(\mathrm{dist}(j,i)\) とすると、

\(H'_i \leq H_j + D \times \mathrm{dist}(j,i)\)

が成り立ちます。

よって、すべての \(j\) から来る上限の最小値

\(F_i = \min_j \left( H_j + D \times \mathrm{dist}(j,i) \right)\)

が、花 \(i\) の取り得る最大の高さになります。

この \(F_i\) を全ての \(i\) について求めれば、答えは

\(\sum_i F_i\)

です。

---

ただし、すべての \(i,j\) の組を調べると \(O(N^2)\) になり、\(N \leq 2 \times 10^5\) では間に合いません。

そこで、左から来る制約と右から来る制約を分けて計算します。

アルゴリズム

左側の花だけから受ける制約を考えます。

\(dp_i\) を「位置 \(i\) の花について、位置 \(i\) 以前の花から受ける制約を考えたときの最大値」とします。

位置 \(i\) 自身の元の高さによる制限があるので、まず

\(dp_i \leq H_i\)

です。

また、位置 \(i\) の直前に制約を伝えてくる花は、位置 \(i-L\) から \(i-1\) のどこかにあります。
その中で最も小さい \(dp\) を持つ花から制約を受けるのが一番厳しいので、

\(dp_i = \min \left( H_i,\ \min_{i-L \leq p < i} dp_p + D \right)\)

となります。

この式をそのまま計算すると、各 \(i\) について最大 \(L\) 個を見るため \(O(NK)\) になってしまいます。

そこで、区間

\([i-L, i-1]\)

の \(dp\) の最小値を高速に求めるために、単調キューを使います。

単調キューには候補となる添字を入れておき、常に \(dp\) の値が小さい順になるように保ちます。
これにより、区間内の最小値はキューの先頭を見るだけで分かります。

---

同じ処理を右側からの制約についても行いたいですが、コードでは配列を反転して同じ calc_left を使っています。

手順は次の通りです。

1. \(L = K - 1\) とする
2. 元の配列に対して calc_left を行い、左からの制約 left を求める
3. 配列を反転する
4. 反転した配列に対して calc_left を行い、右からの制約を求める
5. 元の位置 \(i\) に対応する右からの制約は rleft[N-1-i]
6. 最終的な高さは

\(\min(\mathrm{left}_i,\ \mathrm{right}_i)\)

1. これらを合計する

calc_left の中では、各添字はキューに1回入り、1回出るだけなので、全体で \(O(N)\) です。

計算量

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

実装のポイント

• 答えは最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になるため、long long を使います。

• \(K=1\) のときは \(L=0\) で、どの区間も1本だけなので制約はありません。この場合もコードでは自然に dp[i] = H[i] となります。

• 単調キューでは、範囲外になった添字を先頭から削除します。

  • 0-indexed では、現在位置を i とすると有効範囲は [i-L, i-1]
  • したがって dq.front() < i - L なら削除します。

• キュー内の dp が単調増加になるように、末尾の値が現在の dp[i] 以上なら削除してから i を追加します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<ll> calc_left(const vector<ll>& H, int L, ll D) {
    int N = (int)H.size();
    vector<ll> dp(N);
    deque<int> dq;

    for (int i = 0; i < N; i++) {
        while (!dq.empty() && dq.front() < i - L) dq.pop_front();

        ll v = H[i];
        if (!dq.empty()) v = min(v, dp[dq.front()] + D);
        dp[i] = v;

        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }

    return dp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    ll D;
    cin >> N >> K >> D;

    vector<ll> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    int L = K - 1;

    vector<ll> left = calc_left(H, L, D);

    vector<ll> RH = H;
    reverse(RH.begin(), RH.end());
    vector<ll> rleft = calc_left(RH, L, D);

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += min(left[i], rleft[N - 1 - i]);
    }

    cout << ans << '\n';
    return 0;
}

---

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