概要

\(N\) 個並んだ花壇の水分量を、連続する \(K\) 個への加算操作（コスト \(C\)）を繰り返してすべて \(T\) 以上にする最小コストを求める問題です。

考察

貪欲法（Greedy）の適用

この問題では、左端の花壇から順番に「目標値 \(T\) に足りているか」を確認していく貪欲法が有効です。

ある花壇 \(j\) の水分量が \(T\) 未満であるとき、必ず何らかの操作を行って \(j\) 番目の水分量を増やす必要があります。このとき、操作の範囲（長さ \(K\)）を「できるだけ右側」に寄せて選ぶことで、まだ確認していない右側の花壇の水分量も同時に増やすことができ、将来的に必要な操作回数を最小限に抑えることができます。

具体的には、花壇 \(j\) をカバーする操作の開始位置 \(i\) は \(j-K+1 \leq i \leq j\) の範囲である必要がありますが、右側の花壇への恩恵を最大化するために、可能な限り大きな \(i\) を選ぶのが最適です。

効率的な範囲加算の管理

愚直に「範囲内の \(K\) 個に \(1\) ずつ足す」という操作をシミュレーションすると、最悪の場合 \(O(NK)\) の時間がかかり、制約（\(N=2 \times 10^5\)）では間に合いません。 そこで、スライディングウィンドウ（または差分配列の考え方）を用いて、現在の花壇に影響を及ぼしている操作の合計回数を \(O(1)\) で計算します。

1. current_window_sum という変数で、現在注目している花壇をカバーしている操作の合計回数を保持します。
2. 右に移動する際、範囲から外れた古い操作の回数を current_window_sum から差し引きます。
3. 新しく操作を行う際は、その回数を current_window_sum に加算し、どこで操作を開始したかを記録しておきます。

アルゴリズム

1. 必要な変数を初期化する：
   • x[i] : 花壇 \(i\) を左端として開始した操作の回数
   • current_window_sum : 現在の花壇をカバーしている操作の累計回数
   • total_ops : 全体の操作回数の合計
2. 花壇 \(j = 1\) から \(N\) まで順番に走査する：
   • もし \(j - K \geq 1\) なら、花壇 \(j-K\) で開始された操作はもう花壇 \(j\) をカバーしないため、current_window_sum から x[j-K] を引く。
   • 現在の花壇 \(j\) の水分量を計算する： \(A_j + \text{current\_window\_sum}\)
   • 目標 \(T\) に対して不足分 needed があれば：
     • 操作の開始位置 start_idx を決定する。通常は \(j\) だが、右端を越える場合は \(N-K+1\) とする。
     • total_ops と current_window_sum に needed を加算する。
     • x[start_idx] に needed を記録する。
3. 最終的な答えとして total_ops * C を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 花壇を左から右へ 1 回走査するだけであり、各ステップの処理は定数時間です。
• 空間計算量: \(O(N)\)
  • 各花壇の初期水分量 \(A\) と、操作開始回数を記録する配列 \(x\) のために \(O(N)\) のメモリを使用します。

実装のポイント

• スプリンクラーの設置位置の制限: 花壇 \(j\) が不足しているからといって常に start_idx = j にできるわけではありません。スプリンクラーの右端が \(N\) を超えてはいけないため、開始位置は最大でも \(N-K+1\) に制限されます。

• 大きな値の処理: \(T, A_i, C\) が最大 \(10^9\) と大きいため、答えが 64bit 整数（Python では自動で扱われます）の範囲になることに注意が必要です。

• 高速な入出力: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。”` Subscribed.

  ソースコード

import sys

def solve():
    # 使用するメモリや実行速度を最適化するために、sys.stdin.read().split() を用いて
    # 入力データを一括で読み込み、トークンに分割します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 問題文から与えられるパラメータをパースします。
    # N: 花壇の個数
    # K: スプリンクラーが一度に水をまく範囲
    # T: 目標とする土の水分量
    # C: スプリンクラー1回あたりの水道代
    N = int(input_data[0])
    K = int(input_data[1])
    T = int(input_data[2])
    C = int(input_data[3])
    
    # 各花壇の初期水分量 A_i
    A = list(map(int, input_data[4:]))
    
    # x[i] は、i番目の花壇を始点としてスプリンクラーを作動させた回数を記録します。
    # インデックスを1から始めるためにサイズを N + 1 とします。
    # スプリンクラーの始点として選べる最大のインデックスは N - K + 1 です。
    x = [0] * (N + 1)
    
    # current_window_sum は、現在注目している花壇 j をカバーしている
    # スプリンクラーによる水分上昇量の合計を保持します。
    current_window_sum = 0
    
    # total_ops は、すべての花壇を目標値以上にするために必要な総操作回数です。
    total_ops = 0
    
    # スプリンクラーを作動させることができる右端の開始位置
    limit = N - K + 1
    
    # 左側の花壇から順に、目標水分量 T に達しているか確認していきます。
    for j in range(1, N + 1):
        # スプリンクラーを i 番目から i + K - 1 番目まで作動させたとき、
        # 花壇 j がその範囲外（j < i または j > i + K - 1）になるとき、
        # その操作による水分上昇効果を除外します。
        # ここでは左から右へ進んでいるため、i = j - K の操作が j をカバーしなくなるタイミングです。
        if j - K >= 1:
            # 操作の始点 i は必ず limit 以下であるため、その範囲内であれば減算します。
            if j - K <= limit:
                current_window_sum -= x[j - K]
        
        # 現在の花壇 j の水分量は、初期値 A[j-1] にこれまでの操作による増加分を加えたものです。
        # 目標 T に達するために不足している水分量 needed を計算します。
        needed = T - A[j - 1] - current_window_sum
        
        if needed > 0:
            # 水分が不足している場合、スプリンクラーを作動させます。
            # 貪欲法（Greedy）の考え方に基づき、現在の花壇 j をカバーしつつ、
            # できるだけ右側の花壇にも効果が及ぶように、可能な限り右側の位置を始点として選びます。
            # その始点は、現在の位置 j と、可能な右端 limit のうちの小さい方になります。
            start_idx = j if j < limit else limit
            
            # 不足分を補うために needed 回の操作を行います。
            x[start_idx] += needed
            total_ops += needed
            
            # 新しく追加した操作は、現在の花壇 j もカバーするため、ウィンドウの合計に加算します。
            current_window_sum += needed
            
    # すべての花壇を T 以上にするために必要な最小コスト（総操作回数 × 1回あたりのコスト）を出力します。
    print(total_ops * C)

if __name__ == '__main__':
    solve()

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