概要

各花は低くすることしかできません。
「距離が近い花同士の高さ差が \(D\) 以下」という制約を満たしつつ、各花をできるだけ高く残す問題です。

考察

まず、連続する \(K\) 本の中で最大値と最小値の差が \(D\) 以下であることは、次と同値です。

• 添字の差が \(K-1\) 以下である任意の \(2\) 本の花について、高さの差が \(D\) 以下

以降、\(L=K-1\) とします。

つまり、最終的な高さを \(X_i\) とすると、任意の \(|i-j|\leq L\) について

\[ |X_i-X_j|\leq D \]

である必要があります。

ここで、ある花 \(j\) の元の高さが \(H_j\) であることに注目します。
\(X_j\leq H_j\) なので、花 \(j\) から距離 \(L\) 以内の花は高くても \(H_j+D\) までです。
さらにそこから距離 \(L\) 以内の花は高くても \(H_j+2D\) まで、というように制限が伝播します。

花 \(j\) から花 \(i\) まで、1 回で最大 \(L\) 個分進めると考えると、必要なステップ数は

\[ \left\lceil \frac{|i-j|}{L} \right\rceil \]

です。

したがって、任意の実現可能な最終高さ \(X_i\) は、すべての \(j\) について

\[ X_i \leq H_j + D \left\lceil \frac{|i-j|}{L} \right\rceil \]

を満たす必要があります。

よって、花 \(i\) の高さとして取り得る最大値は

\[ B_i = \min_j \left( H_j + D \left\lceil \frac{|i-j|}{L} \right\rceil \right) \]

になります。

この \(B_i\) は実際に条件を満たします。
なぜなら、\(|i-j|\leq L\) なら、花 \(i\) と花 \(j\) は 1 ステップで移動できる距離なので、

\[ B_i \leq B_j + D \]

かつ

\[ B_j \leq B_i + D \]

が成り立ち、したがって

\[ |B_i-B_j|\leq D \]

となるからです。

つまり、各花を \(B_i\) まで残すのが最適です。

ただし、各 \(i\) についてすべての \(j\) を見ると \(O(N^2)\) になり、\(N\leq 2\times 10^5\) では間に合いません。
そこで、左からの制限と右からの制限をそれぞれ高速に計算します。

アルゴリズム

\(K=1\) の場合、各区間は花 1 本だけなので高さ差は常に \(0\) です。
したがって、答えはそのまま

\[ \sum_i H_i \]

です。

以下では \(K\geq 2\)、つまり \(L=K-1\geq 1\) とします。

左側から伝わる制限を left[i] とします。

\[ left_i = \min_{j\leq i} \left( H_j + D \left\lceil \frac{i-j}{L} \right\rceil \right) \]

これは、次のように DP できます。

\[ left_i = \min \left( H_i,\ \min_{i-L\leq p<i} (left_p + D) \right) \]

意味は以下の通りです。

• 花 \(i\) 自身の元の高さによる制限が \(H_i\)
• 直前の \(L\) 個以内のどこかの花 \(p\) から、制限が \(D\) 増えて伝わる

同様に、右側から伝わる制限を right[i] とします。

\[ right_i = \min_{j\geq i} \left( H_j + D \left\lceil \frac{j-i}{L} \right\rceil \right) \]

これは右から左へ見て、

\[ right_i = \min \left( H_i,\ \min_{i<p\leq i+L} (right_p + D) \right) \]

で計算できます。

最終的に、両側からの制限を同時に満たす必要があるので、花 \(i\) の最適な高さは

\[ \min(left_i, right_i) \]

です。

答えは

\[ \sum_i \min(left_i, right_i) \]

です。

例えば、\(K=3, D=2, H=[10,1,10]\) の場合、\(L=2\) です。
中央の花の高さが最大でも \(1\) なので、左右の花は中央から距離 \(2\) 以内にあり、高くても \(1+2=3\) までになります。
したがって最適な高さは \([3,1,3]\) です。

各 DP では「直前または直後の \(L\) 個の最小値」が必要です。
これは単調キューを使うことで、全体 \(O(N)\) で計算できます。

計算量

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

実装のポイント

単調キューには、候補となる添字を入れます。

左から計算する場合、各 \(i\) について、

1. 範囲外になった添字、つまり \(i-L\) より小さい添字をキューの先頭から削除する
2. キューの先頭が現在の範囲内での left の最小値になる
3. left[i] を計算する
4. left[i] より大きい値を持つ添字をキューの末尾から削除してから、\(i\) を追加する

右から計算する場合も同様に、向きを逆にして処理します。

また、\(K=1\) のときは \(L=0\) となり、今回の DP 式が使えないため、最初に特別扱いします。

ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K, D = map(int, input().split())
    H = list(map(int, input().split()))

    if K == 1:
        print(sum(H))
        return

    L = K - 1

    left = [0] * N
    dq = deque()
    for i in range(N):
        while dq and dq[0] < i - L:
            dq.popleft()

        v = H[i]
        if dq:
            t = left[dq[0]] + D
            if t < v:
                v = t
        left[i] = v

        while dq and left[dq[-1]] >= v:
            dq.pop()
        dq.append(i)

    right = [0] * N
    dq.clear()
    for i in range(N - 1, -1, -1):
        while dq and dq[0] > i + L:
            dq.popleft()

        v = H[i]
        if dq:
            t = right[dq[0]] + D
            if t < v:
                v = t
        right[i] = v

        while dq and right[dq[-1]] >= v:
            dq.pop()
        dq.append(i)

    ans = 0
    for a, b in zip(left, right):
        ans += a if a < b else b

    print(ans)

if __name__ == "__main__":
    main()

---

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