概要

「増やすだけ」で各花壇の本数 \(B_i \ge A_i\) を作り、すべての隣接差が \(|B_i-B_{i+1}| \le K\) となるようにしたとき、追加本数 \(\sum(B_i-A_i)\) の最小値を求めます。

考察

重要な気づき：制約は「全ての点からの下限」を作る

条件 \(|B_i-B_{i+1}| \le K\) は、隣同士だけでなく、離れた \(i,j\) に対しても [ |B_i-B_j| \le K|i-j| ] を意味します（隣接の不等式を足し合わせればよい）。

すると任意の \(i,j\) について [ B_i \ge B_j - K|i-j| \ge A_j - K|i-j| ] が成り立ちます。よって どんな美しい状態でも 必ず [ B_i \ge \max_j (A_j - K|i-j|) ] を満たす必要があります。

ここで [ C_i := \max_j (A_j - K|i-j|) ] と置くと、これは「絶対に必要な下限」を各 \(i\) で集めたものです。

では \(C_i\) 自体が美しい状態になるか？

各 \(j\) について関数 \(f_j(i)=A_j-K|i-j|\) は、\(i\) を 1 動かすと値が高々 \(K\) しか変わらない（\(K\)-Lipschitz）です。
そして \(K\)-Lipschitz な関数の最大値もまた \(K\)-Lipschitz なので、\(C_i=\max_j f_j(i)\) も [ |Ci-C{i+1}| \le K ] を満たします。さらに \(j=i\) を取れば \(C_i \ge A_i\) でもあります。

つまり \(C\) は「美しい状態」を満たす上に、全ての解 \(B\) に対して \(B_i \ge C_i\) が成り立つので、\(C\) が各 \(i\) で最小、ひいては追加本数合計も最小になります。

素朴案が厳しい理由

\(C_i=\max_j(A_j-K|i-j|)\) をそのまま計算すると、各 \(i\) に対して全 \(j\) を見るため \(O(N^2)\) になり、\(N \le 2\times 10^5\) では間に合いません。

そこで、この最大値を 左右に分けて \(O(N)\) で計算します。

アルゴリズム

求めたいのは [ C_i=\max_j(A_j-K|i-j|) ] です。\(j \le i\) と \(j \ge i\) に分けます。

1) 左側（\(j \le i\)）からの寄与

[ A_j-K(i-j)= (Aj+Kj)-Ki ] なので [ \max{j\le i}(Aj-K(i-j)) = \left(\max{j\le i}(A_j+Kj)\right)-Ki ] よって、\(A_j+Kj\) の prefix 最大値を持っておけばよいです。

コードでは - pref[i] = max_{j<=i}(A[j] + K*j) - 左からの下限 c_left = pref[i] - K*i

2) 右側（\(j \ge i\)）からの寄与

[ A_j-K(j-i)= (Aj-Kj)+Ki ] なので [ \max{j\ge i}(Aj-K(j-i)) = \left(\max{j\ge i}(A_j-Kj)\right)+Ki ] よって、\(A_j-Kj\) の suffix 最大値を持てばよいです。

コードでは - suf[i] = max_{j>=i}(A[j] - K*j) - 右からの下限 c_right = suf[i] + K*i

3) 合成して \(C_i\) を作る

[ Ci = \max(c_left, c_right) ] 最後に答えは [ \sum{i=1}^N (C_i - A_i) ] です（\(C_i \ge A_i\) が保証される）。

計算量

• 時間計算量: \(O(N)\)（prefix/suffix の 2 回の走査＋集計）
• 空間計算量: \(O(N)\)（pref, suf 配列）

実装のポイント

• \(A_i, K, N\) が大きいので、値は \(10^9 + 10^9\cdot 2\times10^5\) 程度になり得ます。Python なら問題ありませんが、他言語では 64bit 整数が必須です。

• pref[i] - K*i や suf[i] + K*i の形にするため、先に A[i] + K*i / A[i] - K*i の最大値を累積して持つのがコツです。

• 入力が大きいので sys.stdin.buffer.read() で高速に読み取っています。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    pref = [0] * N
    best = -10**30
    for i, a in enumerate(A):
        v = a + K * i
        if v > best:
            best = v
        pref[i] = best

    suf = [0] * N
    best = -10**30
    for i in range(N - 1, -1, -1):
        v = A[i] - K * i
        if v > best:
            best = v
        suf[i] = best

    ans = 0
    for i, a in enumerate(A):
        c = pref[i] - K * i
        t = suf[i] + K * i
        if t > c:
            c = t
        ans += c - a

    print(ans)

if __name__ == "__main__":
    main()

---

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