概要

長さ \(N\) の配列 \(A\) に対し、「連続する \(K\) 個をまとめて \(+1\)」という操作を最小回数で行って、すべての要素を \(T\) 以上にする問題です。最小操作回数に \(C\) を掛けたものが最小コストになります。

考察

重要な気づき

左から順に花壇を見ていくと、位置 \(i\) の値を増やせる操作は「開始位置が \(i-K+1\) から \(i\) の区間」だけです。特に、左から処理しているときに 位置 \(i\) を含む操作で、これから新たに始められるのは開始位置 \(i\) の操作しかありません（開始位置が \(i+1\) 以降の操作は \(i\) を含まないため）。

したがって、左から順に見ていったときに - その時点の水分量がすでに \(T\) 以上なら何もしない - \(T\) 未満なら、不足分 \(T-\text{現在値}\) だけ 開始位置 \(i\) の操作を行うのが必須（そうしないと位置 \(i\) をもう二度と増やせない）

という「強制される」貪欲が成立します。これにより操作回数は自動的に最小になります。

素朴なアプローチが遅い理由

愚直に「操作を行うたびに区間 \(K\) 個を全部 \(+1\)」を実際に配列更新すると、1回の操作が \(O(K)\) かかります。操作回数が大きいケースでは合計が \(O(NK)\) 級になり、\(N \le 2\times 10^5\) では確実に間に合いません。

どう解決するか

区間加算は「差分配列（いもす法）」で管理します。

• 「現在位置に累積でどれだけ足されているか」だけ分かれば、\(A_i\) の実際の値は \(A_i + \text{add}\) で計算できる
• ある位置 \(i\) で \(need\) 回操作をする（区間 \([i, i+K-1]\) に \(+need\)）なら、
  • その場以降の累積加算 \(\text{add}\) に \(+need\) を加える
  • ただし効果は \(K\) 個先で切れるので、\(i+K\) に「\(-need\) する予約」を入れる

これで各 \(i\) を \(O(1)\) で処理でき、全体 \(O(N)\) になります。

アルゴリズム

1. 差分配列 diff を用意し、累積加算量 add = 0、操作回数 ops = 0 で初期化する。
2. 左から \(i=0..N-1\) を順に処理する：
   • add += diff[i] として、ここまでの予約（加算効果の終了など）を反映する。
   • 現在の水分量は cur = A[i] + add。
   • もし cur < T なら不足分 need = T - cur が必ず必要：
     • ops += need（操作回数を増やす）
     • add += need（以降の位置は即座に \(+need\) された状態になる）
     • diff[i+K] -= need（\(K\) 個先で効果が切れるように予約）
3. 最小コストは ops * C を出力する。

（例） \(K=3\) で \(i=2\) から \(need=5\) 回操作すると、位置 \(2,3,4\) がそれぞれ \(+5\)。差分では「今から先は \(+5\) された」として add += 5、そして位置 \(5\) で効果を消すため diff[5] -= 5 とします。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（diff 配列）

実装のポイント

• diff[i+K] にアクセスするため、diff の長さは少なくとも \(N+K+1\) 程度確保しておくと安全です。

• 操作回数 ops や ops * C は最大で大きくなるため、Python の int（任意精度）を使えばオーバーフローは問題ありません（他言語では 64bit 整数が必要）。

• 入力が大きいので sys.stdin.buffer.read() で高速に読む実装にしています。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    T = next(it)
    C = next(it)
    A = [next(it) for _ in range(N)]

    diff = [0] * (N + K + 1)
    add = 0
    ops = 0

    for i in range(N):
        add += diff[i]
        cur = A[i] + add
        if cur < T:
            need = T - cur
            ops += need
            add += need
            diff[i + K] -= need

    print(ops * C)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。