概要

長さ \(N\) の整数列 \(A\) から、長さ \(W\) の連続する部分列（区間）を選び、その「区間の総和」に「区間内の最小値 \(\times K\)」を加えた値の最大値を求める問題です。

考察

この問題の肝は、すべての区間（全部で \(N-W+1\) 個あります）に対して、「区間の総和」と「区間の最小値」をいかに効率よく求めるかという点にあります。

1. 素朴な方法

各区間 \(l\) について、その都度 \(W\) 個の要素を足し合わせ、最小値を探索すると、1つの区間あたり \(O(W)\) の時間がかかります。全体の計算量は \(O(N \times W)\) となり、制約の \(N=5 \times 10^5\) では実行時間制限に間に合いません。

2. 区間和の効率化（スライディングウィンドウ）

区間を 1 つ右にずらすとき、和の変化は「新しく入る要素を足し、範囲外になった要素を引く」だけで計算できます。これにより、各ステップ \(O(1)\) で区間和を更新できます。

3. 区間最小値の効率化（スライディングウィンドウ最小値）

区間の最小値を効率的に求める手法として、「スライディングウィンドウ最小値（Monotonic Queue）」というアルゴリズムがあります。 デック（両端キュー）を使い、以下の条件を維持しながら要素を管理します。 - デックの中身は、値が昇順になるようにインデックスを保持する。 - 新しい要素 \(A_i\) を追加する際、末尾にある \(A_i\) 以上の要素は「今後最小値になる可能性がない」ため、すべて取り除く。 - 範囲外になった（左端から外れた）インデックスを先頭から取り除く。

この手法を使うと、デックの先頭が常に現在の区間の最小値のインデックスを指すようになり、各ステップならし \(O(1)\) で最小値を取得できます。

アルゴリズム

1. 最初の長さ \(W\) の区間について、総和を計算し、スライディングウィンドウ最小値のアルゴリズムでデックを構築します。
2. 最初の区間の評価値 \(\text{sum} + K \times \min\) を計算し、暫定の最大値とします。
3. 区間を 1 つずつ右にずらしながら、以下の操作を繰り返します。
   • 区間和を更新する：current_sum += A[i] - A[i-W]
   • デックの先頭が範囲外（i-W）なら取り除く。
   • A[i] より大きいデック末尾の要素を削除し、i を追加する。
   • current_sum + K * A[dq[0]] を計算し、最大値を更新する。
4. 最終的な最大値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素はデックに高々 1 回追加され、1 回取り除かれます。全体のループも \(N\) 回であるため、線形時間で動作します。
• 空間計算量: \(O(N)\)
  • 数列 \(A\) の保存およびデックの管理に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

• K の符号: \(K\) が負の場合でも、このアルゴリズムは正しく動作します。\(K\) が負であれば「最小値がより小さい（負の方向に大きい）」ほど評価値が大きくなる可能性がありますが、スライディングウィンドウ最小値は常に正確な最小値を返すため、そのまま数式に当てはめるだけで問題ありません。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    # 大量のデータを扱うため、sys.stdin.read().split() が高速です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 数列の長さ, W: 区間の長さ, K: 最小値に掛ける係数
    n = int(input_data[0])
    w = int(input_data[1])
    k = int(input_data[2])
    
    # 数列 A を整数のリストとして読み込みます
    a = list(map(int, input_data[3:]))
    
    # スライディングウィンドウを用いて各区間の総和と最小値を効率的に求めます
    # dq は現在のウィンドウ内の最小値の候補となる要素のインデックスを保持するデックです
    dq = deque()
    
    # 最初のウィンドウ（インデックス 0 から W-1）の処理
    current_sum = sum(a[:w])
    for i in range(w):
        val = a[i]
        # デック内の要素のうち、現在の要素以上のものは最小値になり得ないため取り除きます
        while dq and a[dq[-1]] >= val:
            dq.pop()
        dq.append(i)
    
    # 最初の区間の評価値を計算し、最大値の初期値とします
    # 評価値 = 区間の総和 + K * 区間の最小値
    max_eval = current_sum + k * a[dq[0]]
    
    # ウィンドウを 1 つずつ右にずらしながら評価値を計算します
    # i は新しくウィンドウに入る要素のインデックスです
    for i in range(w, n):
        # ウィンドウの総和を更新：新しい要素を加え、範囲外になった要素を引きます
        val = a[i]
        current_sum += val - a[i - w]
        
        # デックの先頭がウィンドウの範囲外（インデックス i-w）になった場合は取り除きます
        if dq[0] == i - w:
            dq.popleft()
        
        # デックを維持：現在の要素 val 以上の要素を末尾から取り除き、現在のインデックスを追加します
        while dq and a[dq[-1]] >= val:
            dq.pop()
        dq.append(i)
        
        # 現在のウィンドウの評価値を計算し、最大値を更新します
        # a[dq[0]] は常に現在のウィンドウ内での最小値となります
        current_eval = current_sum + k * a[dq[0]]
        if current_eval > max_eval:
            max_eval = current_eval
            
    # 結果を出力します
    sys.stdout.write(str(max_eval) + '\n')

if __name__ == '__main__':
    solve()

---

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