概要

長さ \(N\) の整数列から連続する \(W\) 個の要素からなる区間を選び、区間内の要素の総和に区間内の最小値と \(K\) の積を加えた評価値の最大値を求める問題です。

考察

素朴なアプローチでは、全ての可能な区間（\(N - W + 1\) 個）について、毎回区間内の最小値を計算すると、最小値の計算に \(O(W)\) かかるため、全体で \(O(NW)\) の時間がかかり、\(N\) と \(W\) が最大 \(5 \times 10^5\) である本問題では制限時間内に解くことができません。

そこで、区間内の最小値を効率的に求める必要があります。スライディングウィンドウ内の最小値を高速に求めるには、両端キュー（deque）を用いたスライディングウィンドウ最小値のアルゴリズムが有効です。このアルゴリズムを使うことで、各区間の最小値を \(O(1)\) で取得できます。

アルゴリズム

1. 累積和の事前計算: 各区間の総和を高速に計算するために、長さ \(N+1\) の累積和配列 prefix を作成します。prefix[i] = A[0] + A[1] + ... + A[i-1] となります。
2. スライディングウィンドウ最小値の計算: 両端キュー（deque）を用いて、現在のウィンドウ内の最小値のインデックスを保持します。キューは次のように操作します：
   • ウィンドウから外れたインデックスをキューから削除（先頭から）
   • 新しい要素がキュー内の末尾の要素以上なら、末尾を削除（より小さい値が来たときのために）
   • 現在のインデックスをキューに追加
3. 評価値の計算: 各ウィンドウ位置について、累積和から総和を計算し、キュー先頭のインデックスの値を最小値として用いて評価値を計算します。最大値を更新しながら全ウィンドウを走査します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素は高々1回キューに追加され、1回削除されるため
• 空間計算量: \(O(N)\)
  • 累積和配列とキューに \(O(N)\) の空間が必要

実装のポイント

• 累積和配列はインデックス \(0\) を \(0\) とし、\(i\) 番目の要素までの和を prefix[i+1] に格納することで、区間 \([l, r]\) の和を prefix[r+1] - prefix[l] で簡単に計算できます。

• キューにはインデックスを格納し、実際の値は配列 A から参照します。

• ウィンドウの開始位置 l は i - W + 1 で計算でき、i が \(W-1\) 以上になったときから評価値の計算を開始します。

• 初期値の max_val は非常に小さい値（\(-10^{18}\)）に設定し、負の評価値も正しく扱えるようにします。

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0]); W = int(data[1]); K = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    if W == 0:
        print(0)
        return
        
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    dq = deque()
    max_val = -10**18
    
    for i in range(N):
        while dq and dq[0] < i - W + 1:
            dq.popleft()
            
        while dq and A[dq[-1]] >= A[i]:
            dq.pop()
            
        dq.append(i)
        
        if i >= W - 1:
            l = i - W + 1
            total = prefix[i + 1] - prefix[l]
            min_val = A[dq[0]]
            value = total + K * min_val
            if value > max_val:
                max_val = value
                
    print(max_val)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。