概要

隣り合う花壇の花の本数の差が \(K\) 以下になるように、花を追加する最小本数を求める問題です。花を抜くことはできないため、各花壇の花の本数は増やすことしかできません。

考察

重要な気づき

1. 花は抜けない: 各花壇 \(i\) の最終的な花の本数を \(B_i\) とすると、\(B_i \geq A_i\) という制約があります。
2. 隣接制約: すべての隣り合う花壇について \(|B_i - B_{i+1}| \leq K\) を満たす必要があります。
3. 最小化: 追加する花の総数 \(\sum_{i=1}^{N} (B_i - A_i)\) を最小化したいです。

制約の言い換え

\(|B_i - B_{i+1}| \leq K\) は以下の2つの条件に分解できます： - \(B_{i+1} \geq B_i - K\)（右隣は左の花壇より \(K\) 以上少なくならない） - \(B_i \geq B_{i+1} - K\)（左隣は右の花壇より \(K\) 以上少なくならない）

両方向からの制約

例えば、\(A = [10, 1, 10]\)、\(K = 2\) の場合を考えます。 - 左から見ると：\(B_1 = 10\) なら \(B_2 \geq 10 - 2 = 8\) - 右から見ると：\(B_3 = 10\) なら \(B_2 \geq 10 - 2 = 8\)

このように、ある花壇の値は左右両方からの制約を受けます。

アルゴリズム

Step 1: 左からの制約を計算

配列 left_min[i] を定義します。これは「左側からの制約だけを考えたとき、\(B_i\) が取るべき最小値」です。

• \(\text{left\_min}[0] = A_0\)
• \(\text{left\_min}[i] = \max(A_i, \text{left\_min}[i-1] - K)\)

\(B_i \geq B_{i-1} - K\) という制約と \(B_i \geq A_i\) という制約を組み合わせています。

Step 2: 右からの制約を計算

同様に配列 right_min[i] を定義します。

• \(\text{right\_min}[N-1] = A_{N-1}\)
• \(\text{right\_min}[i] = \max(A_i, \text{right\_min}[i+1] - K)\)

Step 3: 両方の制約を統合

各花壇 \(i\) の最終的な花の本数は、両方の制約を満たす必要があるため：

\[B_i = \max(\text{left\_min}[i], \text{right\_min}[i])\]

Step 4: 答えの計算

追加する花の総数は：

\[\sum_{i=0}^{N-1} (B_i - A_i)\]

計算量

• 時間計算量: \(O(N)\)
  • 左からの走査で \(O(N)\)
  • 右からの走査で \(O(N)\)
  • 最終的な計算で \(O(N)\)
• 空間計算量: \(O(N)\)
  • left_min、right_min、B の各配列に \(O(N)\)

実装のポイント

1. max 関数の活用: 各制約を max で表現することで、「増やすことしかできない」という条件と「隣との差が \(K\) 以下」という条件を自然に扱えます。

2. 両方向の走査: 片方向だけでは不十分です。例えば左から右への走査だけでは、右側の大きな値から来る制約を見落とします。

3. \(N = 1\) の特殊ケース: 花壇が1つだけの場合、隣り合う花壇が存在しないため、何も追加する必要がありません（この実装では自然に処理されます）。

   ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    total_flowers = 0
    
    for i in range(N - 1):
        diff = A[i + 1] - A[i]
        
        if diff > K:
            # A[i+1] が A[i] より K を超えて大きい場合
            # A[i] を増やす必要がある
            # A[i] を A[i+1] - K にする
            needed = diff - K
            A[i] = A[i + 1] - K
            total_flowers += needed
        elif diff < -K:
            # A[i] が A[i+1] より K を超えて大きい場合
            # A[i+1] を増やす必要がある
            # A[i+1] を A[i] - K にする
            needed = -diff - K
            A[i + 1] = A[i] - K
            total_flowers += needed
    
    # 逆方向にも確認（右から左へ）
    # 実際には、左から右への一回のパスで A[i] を増やした場合、
    # それが左側の条件を壊す可能性がある
    
    # 再度左から右へ確認
    for i in range(N - 1):
        diff = A[i + 1] - A[i]
        if diff > K:
            needed = diff - K
            A[i] = A[i + 1] - K
            total_flowers += needed
        elif diff < -K:
            needed = -diff - K
            A[i + 1] = A[i] - K
            total_flowers += needed
    
    print(total_flowers)

# 別のアプローチ：各位置での最小必要値を計算
def solve_v2():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    # B[i] は花壇 i の最終的な花の本数（B[i] >= A[i]）
    # 条件: |B[i] - B[i+1]| <= K
    # 最小化: sum(B[i] - A[i])
    
    # 左から右へ: B[i+1] >= B[i] - K だが B[i+1] >= A[i+1] なので
    #             B[i+1] >= max(A[i+1], B[i] - K)
    # 右から左へ: B[i] >= B[i+1] - K だが B[i] >= A[i] なので
    #             B[i] >= max(A[i], B[i+1] - K)
    
    # 左からの最小値を計算
    left_min = [0] * N
    left_min[0] = A[0]
    for i in range(1, N):
        # B[i] >= A[i] かつ B[i] >= B[i-1] - K
        left_min[i] = max(A[i], left_min[i-1] - K)
    
    # 右からの最小値を計算
    right_min = [0] * N
    right_min[N-1] = A[N-1]
    for i in range(N-2, -1, -1):
        # B[i] >= A[i] かつ B[i] >= B[i+1] - K
        right_min[i] = max(A[i], right_min[i+1] - K)
    
    # 各位置での最終値は max(left_min[i], right_min[i]) の制約を満たす必要がある
    # しかし、実際には left_min と right_min の両方の制約を満たす最小値
    
    # B[i] = max(left_min[i], right_min[i]) とすると条件を満たすか？
    # 実は、B[i] >= max(A[i], left からの制約, right からの制約)
    
    total = 0
    B = [max(left_min[i], right_min[i]) for i in range(N)]
    
    for i in range(N):
        total += B[i] - A[i]
    
    print(total)

solve_v2()

---

この解説は claude4.5opus によって生成されました。