概要

一列に並んだ花壇の水分量を、連続する \(K\) 個の区間に水をまく操作で目標値 \(T\) 以上にしたいとき、必要な最小コストを求める問題。

考察

各花壇 \(i\) に対して、目標値 \(T\) までの不足分 \(d_i = \max(0, T - A_i)\) を求めると、この問題は「各区間に対し、連続する \(K\) 個の要素に \(1\) を加える操作を何回行うか」という操作回数最小化問題に帰着される。

素朴な方法として、左から順に「不足している場所があればその区間に操作を行う」と考えられる。しかし、単純にシミュレーションすると、同じ区間に対して何度もループ内で加算処理を行うため、最悪計算量が \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では間に合わない。

そこで、imos法（差分更新法） を活用して、区間への一括加算を高速に行う工夫をする。具体的には、操作の開始地点に \(+x\)、終了地点の次の位置に \(-x\) を記録し、累積和の要領で現在の効果を管理する。

このようにして、各位置での「現在の水分補給量」を効率的に管理しながら、必要なだけ操作を行うことで全体を線形時間で処理できる。

アルゴリズム

1. 各花壇の必要水分量 \(d_i = \max(0, T - A_i)\) を計算。
2. 左から順番に走査しながら、以下を繰り返す：
   • 現在位置にすでにかかっている操作回数 current_add を管理（差分更新で計算）。
   • 必要な水分量が満たされていなければ、その分だけ操作を行う。
   • 操作は区間 \([i, i+K-1]\) に行うため、差分配列 operations の \(i\) 番目に \(+\text{needed}\)、\(i+K\) 番目に \(-\text{needed}\) を記録。
3. 全体の操作回数 total_ops に必要なコスト \(C\) をかけて出力。

このアルゴリズムにより、必要な操作回数を前から貪欲に決定しつつ、区間更新を効率的に行える。

計算量

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

実装のポイント

• 差分配列 operations はサイズを \(N+1\) にしておくと、範囲外アクセスを防ぎやすい。
• current_add は差分の累積和のように更新することで、現在の位置に適用されている操作回数が高速に得られる。
• 最終的なコストは操作回数 total_ops に \(C\) をかけたもの。

## ソースコード

```python
import sys
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    T = int(data[2])
    C = int(data[3])
    A = list(map(int, data[4:]))
    
    # 各花壇が必要とする追加水分量
    diff = [max(0, T - a) for a in A]
    
    # 累積和を使って効率的に範囲和を計算
    # 各位置で必要な最小操作回数をシミュレーション
    
    # 差分配列を使って操作の影響を管理
    # 操作は連続K個に+1するので、差分更新が有効
    
    # 最小コストを求める
    # 貪欲法：左から順に、必要ならその位置からK個に操作を行う
    
    operations = [0] * (N + 1)  # 差分用の配列、N+1にすることで範囲外アクセス防止
    total_ops = 0
    current_add = 0  # 現在の位置に適用されている操作の合計
    
    for i in range(N):
        current_add += operations[i]
        needed = diff[i] - current_add
        if needed > 0:
            total_ops += needed
            current_add += needed
            if i + K <= N:
                operations[i + K] -= needed
                
    print(total_ops * C)

if __name__ == "__main__":
    main()

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