概要

\(N\) 個の花壇に対し、隣り合う花壇の花の本数の差を \(K\) 以下にするために必要な「追加する花の最小本数」を求める問題です。花を減らすことはできず、増やすことのみが許されています。

考察

美しい花壇の条件は、すべての \(i\) について \(|A_i - A_{i+1}| \leq K\) であることです。 絶対値を外すと、この条件は以下の2つの不等式に分解できます。

1. \(A_{i+1} \geq A_i - K\) （右側の花壇は、左側より極端に少なくない）
2. \(A_i \geq A_{i+1} - K\) （左側の花壇は、右側より極端に少なくない）

花を「抜くことができない（増やすことしかできない）」という制約があるため、条件を満たさない場合は 「少ない方の花壇に花を足して、差をちょうど \(K\) にする」 のが最適です。

例えば、\(A = [10, 1], K = 2\) の場合を考えます。 左から右へ見ていくと、\(A_2\) は最低でも \(A_1 - K = 8\) 本必要です。したがって、\(A_2\) を \(8\) に更新します。 逆に、\(A = [1, 10], K = 2\) の場合は、右から左へ見ていくと、\(A_1\) は最低でも \(A_2 - K = 8\) 本必要になります。

このように、「左から右への走査」で条件1を、「右から左への走査」で条件2を満たすように順次更新していくことで、最小の追加本数で全体の条件を満たすことができます。

アルゴリズム

1. 現在の花の本数を管理する配列 \(b\) を用意します（初期値は \(A\) ）。
2. 前方向の走査（左から右へ）: \(i = 1\) から \(N-1\) まで順に、 \(b[i] < b[i-1] - K\) であれば、 \(b[i] = b[i-1] - K\) と更新します。
3. 後ろ方向の走査（右から左へ）: \(i = N-2\) から \(0\) まで順に、 \(b[i] < b[i+1] - K\) であれば、 \(b[i] = b[i+1] - K\) と更新します。
4. 最終的な配列 \(b\) の合計値から、元の配列 \(A\) の合計値を引いたものが答えとなります。

計算量

• 時間計算量: \(O(N)\) 配列を前から後ろに1回、後ろから前に1回走査するだけなので、要素数 \(N\) に対して線形時間で計算が終わります。\(N = 2 \times 10^5\) であっても十分高速です。
• 空間計算量: \(O(N)\) 入力された花の本数を保持するための配列のサイズに依存します。

実装のポイント

• 合計値の計算: 答えが非常に大きな値（最大で \(N \times 10^9 \approx 2 \times 10^{14}\) 程度）になる可能性があるため、言語によっては 64bit 整数型（Python の場合は自動で対応されます）を使用する必要があります。

• 2回の走査: 1回の走査だけでは、更新された値がさらに隣の値を更新しなければならないケース（連鎖的な更新）に対応しきれません。必ず双方向からの走査が必要です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 花壇の数, K: 許容される花の本数の差
    n = int(input_data[0])
    k = int(input_data[1])
    
    # a: 各花壇の現在の花の本数
    # map関数を使用して一括で整数に変換することで効率化します
    a = list(map(int, input_data[2:]))
    
    # b: 最終的な花の本数を格納するリスト
    # 最初は現在の本数 a で初期化します
    b = list(a)
    
    # 前方向への走査:
    # すべての i について b[i] >= b[i-1] - k を満たすように調整します
    # これにより、b[i-1] - b[i] <= k が保証されます
    for i in range(1, n):
        target = b[i-1] - k
        if b[i] < target:
            b[i] = target
            
    # 後ろ方向への走査:
    # すべての i について b[i] >= b[i+1] - k を満たすように調整します
    # これにより、b[i+1] - b[i] <= k が保証されます
    # 前方向の走査の結果を維持しつつ調整することで、最終的にすべての隣り合う差が K 以下になります
    for i in range(n-2, -1, -1):
        target = b[i+1] - k
        if b[i] < target:
            b[i] = target
    
    # 追加が必要な花の最小本数は、調整後の総本数から元の総本数を引いたものです
    # Pythonの整数型は自動的に多倍長整数として扱われるため、大きな値でも溢れることはありません
    print(sum(b) - sum(a))

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。