概要

連続する \(K\) 個の花壇に水をまく操作を繰り返して、すべての花壇の水分量を目標値 \(T\) 以上にするための最小コストを求める問題です。貪欲法といもす法を組み合わせて効率的に解きます。

考察

重要な気づき

1. 左から順に処理する貪欲法が最適

   • 左端の花壇から順に見ていき、水分が足りない花壇があれば、その花壇を左端とする区間に水をまくのが最適です。
   • なぜなら、より右側を左端にすると、現在の花壇に水が届かなくなってしまうからです。

2. 具体例で考える

   • \(N=5, K=3, T=10\) で、各花壇の必要追加水分量が [3, 2, 5, 1, 4] だとします。
   • 位置0: 3回水をまく（区間[0,1,2]に効果）
   • 位置1: すでに3の効果があるので、不足なし
   • 位置2: 3の効果があるが、5必要なので2回追加（区間[2,3,4]に効果）
   • 以降も同様に処理…

素朴なアプローチの問題点

各操作ごとに \(K\) 個の花壇の値を更新すると、最悪 \(O(N \times T \times K)\) となり、\(T\) が \(10^9\) まであるため TLE になります。

解決策：いもす法

「区間に一様に値を加算する」操作を効率化するためにいもす法を使います。 - 区間 \([i, i+K-1]\) に \(x\) を加算する代わりに、差分配列で diff[i] += x, diff[i+K] -= x と記録 - 累積和を取ることで、各位置での実際の加算量を \(O(1)\) で計算できます

アルゴリズム

1. 各花壇で必要な追加水分量 need[i] = max(0, T - A[i]) を計算

2. 差分配列 diff と累積水やり量 current_water を用意

3. 左から順に各花壇 \(i\) を処理：

   • current_water += diff[i] で現在位置での累積効果を更新
   • shortage = need[i] - current_water で不足量を計算
   • shortage > 0 なら：
     • shortage 回の操作を行う
     • current_water += shortage で現在位置の効果を更新
     • diff[i + K] -= shortage で効果の終了位置を記録

4. 総操作回数 × \(C\) を出力

例: N=5, K=3, need=[3, 2, 5, 1, 4]

i=0: shortage=3, 3回操作, diff[3]-=3
i=1: current_water=3, shortage=2-3<0, 操作不要
i=2: current_water=3, shortage=5-3=2, 2回操作, diff[5]-=2
i=3: current_water=3+(-3)+2=2, shortage=1-2<0, 操作不要
i=4: current_water=2, shortage=4-2=2, 2回操作

合計: 3+2+2=7回

計算量

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

  • 各花壇を1回ずつ処理するだけ

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

  • 差分配列と必要水分量の配列に \(O(N)\)

実装のポイント

1. いもす法の終端処理: 効果の終了位置 i + K が配列範囲外にならないよう、diff のサイズを \(N+1\) にするか、範囲チェックを行う

2. 累積和のリアルタイム計算: 通常のいもす法は最後に累積和を取りますが、この問題では処理しながら累積和を計算することで、1パスで解けます

3. オーバーフロー対策: 総操作回数と \(C\) の積が大きくなる可能性があるため、Python以外の言語では64ビット整数を使用する必要があります

   ソースコード

def solve():
    N, K, T, C = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 各花壇で必要な追加水分量を計算
    need = [max(0, T - a) for a in A]
    
    # 貪欲法 + いもす法で解く
    # 左から順に見ていき、水分が足りない花壇があれば、
    # その花壇を左端とする区間に水をまく
    
    # diff[i]: 位置iでの水やり効果の変化量（いもす法用）
    diff = [0] * (N + 1)
    current_water = 0  # 現在の位置での累積水やり量
    total_operations = 0
    
    for i in range(N):
        # いもす法で現在位置での水やり効果を更新
        current_water += diff[i]
        
        # 現在の花壇で不足している水分量
        shortage = need[i] - current_water
        
        if shortage > 0:
            # shortage回の操作が必要
            total_operations += shortage
            current_water += shortage
            
            # この操作の効果は位置 i から i+K-1 まで
            # 位置 i+K で効果が終わる
            end_pos = i + K
            if end_pos <= N:
                diff[end_pos] -= shortage
    
    print(total_operations * C)

solve()

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