E - 区間の評価値 / Interval Evaluation Value 解説 by admin
Claude 4.6 Opus (Thinking)概要
長さ \(N\) の数列から連続する \(W\) 個の要素を選び、「区間の総和 \(+\) \(K\) \(\times\) 区間の最小値」で定義される評価値を最大化する問題です。スライディングウィンドウ最小値（単調デック）を用いて \(O(N)\) で解けます。
考察
評価値の構造
区間 \([l, l+W-1]\) の評価値は次の式で表されます：
\[\text{評価値} = \sum_{i=l}^{l+W-1} A_i + K \times \min(A_l, \ldots, A_{l+W-1})\]
この値を全てのウィンドウ位置 \(l\) について計算し、最大値を求める必要があります。
素朴なアプローチの問題点
各ウィンドウについて愚直に総和と最小値を求めると、1つのウィンドウあたり \(O(W)\) かかり、ウィンドウは \(N - W + 1\) 個あるので、全体で \(O(NW)\) となります。\(N\) が最大 \(5 \times 10^5\) のとき、\(W\) が大きいと間に合いません。
高速化のアイデア
- 区間の総和：累積和（prefix sum）を前計算しておけば、各ウィンドウの総和を \(O(1)\) で求められます。
- 区間の最小値：スライディングウィンドウ最小値を 単調デック（monotone deque） で管理すれば、各ウィンドウの最小値を償却 \(O(1)\) で求められます。
これにより全体を \(O(N)\) で処理できます。
アルゴリズム
1. 累積和の前計算
\(\text{prefix}[0] = 0, \quad \text{prefix}[i] = A_1 + A_2 + \cdots + A_i\)
と定義すると、区間 \([l, l+W-1]\)（0-indexed）の総和は \(\text{prefix}[l+W] - \text{prefix}[l]\) で \(O(1)\) で求まります。
2. 単調デックによるスライディングウィンドウ最小値
デック（両端キュー）にインデックスを格納し、対応する \(A\) の値が単調増加になるように管理します。
配列を左から右へ走査しながら、以下の操作を行います：
- 末尾からの除去：新しい要素 \(A[i]\) がデック末尾の要素以下なら、末尾を除去（新しい要素の方が小さいので、古い要素は今後最小値にならない）。
- 追加：\(i\) をデック末尾に追加。
- 先頭からの除去：デック先頭のインデックスがウィンドウ \([i-W+1, i]\) の範囲外なら除去。
- 最小値の取得：デック先頭が現在のウィンドウの最小値のインデックス。
3. 評価値の計算と最大値の更新
ウィンドウが完成する \(i \geq W - 1\) のタイミングで、
\[\text{score} = (\text{prefix}[i+1] - \text{prefix}[i-W+1]) + K \times A[\text{デック先頭}]\]
を計算し、答えを更新します。
具体例
\(A = [3, 1, 4, 1, 5],\ W = 3,\ K = 2\) のとき：
| \(l\) (0-indexed) | 区間 | 総和 | 最小値 | 評価値 |
|---|---|---|---|---|
| 0 | \([3,1,4]\) | \(8\) | \(1\) | \(8 + 2 \times 1 = 10\) |
| 1 | \([1,4,1]\) | \(6\) | \(1\) | \(6 + 2 \times 1 = 8\) |
| 2 | \([4,1,5]\) | \(10\) | \(1\) | \(10 + 2 \times 1 = 12\) |
最大値は \(12\) です。
計算量
- 時間計算量: \(O(N)\)（累積和の構築に \(O(N)\)、デックの操作は各要素が高々1回ずつ追加・除去されるため償却 \(O(N)\)）
- 空間計算量: \(O(N)\)（累積和配列とデックの分）
実装のポイント
デックにはインデックスを格納し、値の比較は \(A[\text{index}]\) で行います。こうすることでウィンドウ範囲外かどうかの判定もインデックスの比較で簡単にできます。
\(K\) が負の場合、最小値が小さいほど \(K \times \min\) は大きくなる（負×負＝正）ため、最小値が小さいウィンドウが有利になることもあります。しかし、このコードは各ウィンドウについて正確に最小値を求めて評価値を計算しているので、\(K\) の符号に関わらず正しく動作します。
答えが非常に大きくなりうる（最大で約 \(5 \times 10^{14}\) 程度）ため、64ビット整数が必要ですが、Python では整数のオーバーフローを心配する必要はありません。
ソースコード
import sys
from collections import deque
def main():
input_data = sys.stdin.buffer.read().split()
N = int(input_data[0])
W = int(input_data[1])
K = int(input_data[2])
A = [int(input_data[3 + i]) for i in range(N)]
# Precompute prefix sums
prefix = [0] * (N + 1)
for i in range(N):
prefix[i + 1] = prefix[i] + A[i]
# For each window starting at l (0-indexed), the score is:
# sum(A[l..l+W-1]) + K * min(A[l..l+W-1])
# = (prefix[l+W] - prefix[l]) + K * min(A[l..l+W-1])
# We need to efficiently compute the minimum of each window of size W.
# But since K can be negative, we might want the maximum instead.
# Actually, we want to maximize: sum + K * min
# If K >= 0, larger min is better (for fixed sum), so we want large min.
# If K < 0, smaller min is worse (makes K*min more negative), so we want large min too? No...
# Actually it's not that simple because different windows have different sums AND different mins.
# Approach: For each possible value of the minimum, consider all windows where that element
# is the minimum. This is a classic approach using a monotone stack.
# Alternative approach: iterate over all windows using a sliding window minimum (deque).
# This is O(N) and straightforward.
# Sliding window min using deque
dq = deque() # stores indices, maintaining A[indices] in increasing order
ans = -float('inf')
for i in range(N):
# Remove elements from back that are >= A[i] (we maintain increasing order for min)
while dq and A[dq[-1]] >= A[i]:
dq.pop()
dq.append(i)
# Remove elements that are out of the window
# Window is [i - W + 1, i]
while dq[0] < i - W + 1:
dq.popleft()
# If we have a full window
if i >= W - 1:
l = i - W + 1
window_sum = prefix[i + 1] - prefix[l]
window_min = A[dq[0]]
score = window_sum + K * window_min
if score > ans:
ans = score
print(ans)
main()
この解説は claude4.6opus-thinking によって生成されました。