概要

長さ \(N\) の数列から長さ \(W\) の連続部分列を選び、その「総和 + 最小値 × \(K\)」という評価値を最大化する問題です。

考察

この問題では、すべての長さ \(W\) の連続部分列について評価値を計算し、その最大値を求めます。

評価値は次のように定義されます： $\( \text{評価値} = \left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l, A_{l+1}, \ldots, A_{l+W-1}) \)$

素朴な方法では、各区間に対して総和と最小値を毎回計算すると、時間計算量が \(O(NW)\) となり、制約 \(N, W \leq 5 \times 10^5\) では間に合いません。

そこで、以下の工夫が必要になります：

• 区間の総和：累積和を用いて \(O(1)\) で求めます。
• 区間の最小値：スライディングウィンドウにおける最小値を効率的に求めるために、双方向キュー（deque） を使用します。

このようにすることで、全体を高速に処理できます。

アルゴリズム

1. 累積和の前処理

   • prefix[i] := \(A_1 + A_2 + \cdots + A_{i-1}\) となる累積和配列を作成します。
   • 区間 \([l, r]\) の和は prefix[r+1] - prefix[l] で \(O(1)\) で取得可能です。

2. スライディングウィンドウでの最小値管理

   • 長さ \(W\) の区間を左から右へ動かしながら、その中の最小値を高速に取得します。
   • deque を使い、以下の条件で管理します：
     • deque の末尾にあるインデックスに対応する要素が現在の要素以上なら削除（最小値候補として不要）
     • deque の先頭のインデックスが区間外なら削除
     • deque の先頭には常に現在の区間の最小値のインデックスが入っている

3. 評価値の計算と更新

   • 各区間 \([l, l+W-1]\) に対して、上記を用いて和と最小値を求め、評価値を計算。
   • 最大の評価値を保持しておき、最後に出力します。

計算量

• 時間計算量: \(O(N)\)
  各要素は deque に一度追加され、一度削除されるだけなので、全体で線形時間。
• 空間計算量: \(O(N)\)
  累積和テーブルと deque に必要な領域。

実装のポイント

• deque にはインデックスを格納し、実際に使うのは A[index] の値。

• 区間がちょうど長さ \(W\) になったとき（r >= W - 1）に評価値を計算する。

• 累積和を使うことで区間和を高速に求めること。

  ソースコード

from collections import deque
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    W = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:]))

    # 累積和を計算
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]

    # 双方向キューを使って、区間 [l, l+W-1] の最小値を効率的に管理
    dq = deque()
    max_value = float('-inf')

    for r in range(N):
        # 現在の値より大きい要素を deque から削除
        while dq and A[dq[-1]] >= A[r]:
            dq.pop()
        dq.append(r)

        # 区間 [l, r] が W より長い場合は左端を削除
        if dq[0] <= r - W:
            dq.popleft()

        # 区間が W になったら評価値を計算
        if r >= W - 1:
            l = r - W + 1
            current_sum = prefix[r + 1] - prefix[l]
            min_val = A[dq[0]]
            value = current_sum + K * min_val
            if value > max_value:
                max_value = value

    print(max_value)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。