概要

一列に並んだ花壇のそれぞれに花の本数が決まっており、隣り合う花壇の花の本数の差が \(K\) 以下になるように花を追加して、全体を「美しい」状態にしたい。すでに植えてある花は抜けないので、必要な最小の追加本数を求めよ。

考察

この問題の核心は、「隣り合う花壇の花の本数の差が \(K\) 以下」という条件を満たすように各花壇の花の本数を調整することです。ただし、花は減らせないので、必要な分だけ増やす必要があります。

素朴なアプローチの問題点

最初に思いつくのは、隣り合う要素を見て条件を満たさない場合に一方を増やすという貪欲法です。しかし、この方法では「後ろから来たときにまた調整が必要」になり、最適な結果を得られない可能性があります。例えば、左から調整した結果、右側とのバランスが崩れるといったことが起こります。

さらに、全探索などで再帰的に調整しようとすると、計算量が爆発してしまいます（指数時間など）。制約が \(N \leq 2 \times 10^5\) なので、線形またはそれに近い時間で解く必要があります。

解決策：前処理と後処理による動的計画法的な考え方

各花壇において、最終的に持っていてほしい花の最小本数を前から見たときの下限と後ろから見たときの下限の両方から求めることで、全体の整合性を保ちつつ最適な解を得ることができます。

前から見る（左→右）

各花壇 \(i\) に対して、左隣の花壇との関係から、花の本数の下限を計算します。つまり、前の花壇が \(x\) 本の花を持っていれば、今の花壇は最低でも \(x - K\) 本必要です（ただし既存の本数 \(A_i\) より小さければ \(A_i\) を採用）。

この処理によって、各位置における左方向からの条件を満たす最小値（left[i]）が得られます。

後ろから見る（右→左）

同様に、右隣の花壇から見て、今の花壇が持つべき下限を計算します。これにより、右方向からの条件を満たす最小値（right[i]）も求められます。

最終的な花の本数

各花壇について、left[i] と right[i] のうち大きい方を最終的な花の本数とすれば、両隣の条件を同時に満たすことができます。

このようにして求めた最終的な花の本数から、既に植わっている本数 \(A_i\) を引いたものが、その花壇に追加すべき花の本数です。

アルゴリズム

1. left配列を作成し、各位置における左隣との関係から最小必要本数を前から計算。
2. right配列を作成し、各位置における右隣との関係から最小必要本数を後ろから計算。
3. 各位置 \(i\) について、\(\max(\text{left}[i], \text{right}[i])\) を最終的な花の本数とする。
4. その値から \(A_i\) を引いたものを合計し、答えとする。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.buffer.readline を使用している。
• left と right の初期化は、それぞれ最初と最後の要素を元の花の本数 \(A_i\) から始めることに注意。
• 最終的な花の本数は max(left[i], right[i]) であり、必ず \(A_i\) 以上になる（条件を満たすために増やすだけなので）。

## ソースコード

```python
import sys

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

    # 前処理: 各位置における左側からの最小増加列の下限
    left = [0] * N
    left[0] = A[0]
    for i in range(1, N):
        left[i] = max(A[i], left[i - 1] - K)

    # 後処理: 各位置における右側からの最小減少列の下限
    right = [0] * N
    right[N - 1] = A[N - 1]
    for i in range(N - 2, -1, -1):
        right[i] = max(A[i], right[i + 1] - K)

    # 各位置で両方の条件を満たす最小値をとり、合計を計算
    ans = 0
    for i in range(N):
        final_height = max(left[i], right[i])
        ans += final_height - A[i]

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。