概要

連続する \(K\) 個の花壇を必ず全て手入れするという制約のもとで、手入れする花壇の美しさの合計を最大化する問題です。スライディングウィンドウを用いて効率的に解くことができます。

考察

基本的な観察

まず、制約がなければ（自由に花壇を選べるなら）、美しさが正の花壇だけを選ぶのが最適です。このときの合計を「全正数の合計」と呼びます。

\[\text{total\_positive} = \sum_{i=1}^{N} \max(0, A_i)\]

しかし本問では、ある連続 \(K\) 個の花壇を全て手入れしなければならないという制約があります。この \(K\) 個の中に美しさが負の花壇が含まれていると、それも強制的に選ばなければなりません。

窓 \([l, l+K-1]\) を固定したときの答え

窓（連続 \(K\) 個の区間）を固定すると：

• 窓の中の花壇: 美しさが正でも負でも必ず手入れする
• 窓の外の花壇: 美しさが正なら手入れし、負なら手入れしない

したがって、窓 \([l, l+K-1]\) を選んだときの美しさの合計は：

\[\text{answer}(l) = \sum_{i \in \text{窓}} A_i + \sum_{\substack{i \notin \text{窓} \\ A_i > 0}} A_i\]

これを変形すると：

\[\text{answer}(l) = \text{total\_positive} - \sum_{i \in \text{窓}} \max(0, -A_i)\]

ここで \(\max(0, -A_i)\) は「ペナルティ」です。\(A_i\) が負のとき、その絶対値がペナルティになります（本来選ばないはずの負の花壇を強制的に選ぶコスト）。\(A_i\) が \(0\) 以上のときペナルティは \(0\) です。

具体例

\(N=5, K=3, A = [3, -2, 5, -4, 1]\) の場合：

• \(\text{total\_positive} = 3 + 5 + 1 = 9\)
• ペナルティ配列: \([0, 2, 0, 4, 0]\)
• 窓 \([1,3]\): ペナルティ合計 \(= 0+2+0 = 2\) → 答え \(9-2=7\)
• 窓 \([2,4]\): ペナルティ合計 \(= 2+0+4 = 6\) → 答え \(9-6=3\)
• 窓 \([3,5]\): ペナルティ合計 \(= 0+4+0 = 4\) → 答え \(9-4=5\)

最大は \(7\) です。

素朴な方法の問題点

各窓ごとにペナルティの合計を毎回 \(O(K)\) で計算すると、全体で \(O(NK)\) となり、\(N, K\) が大きいとTLEになります。

アルゴリズム

1. \(\text{total\_positive}\) を計算する
2. ペナルティ配列 \(\text{penalty}[i] = \max(0, -A_i)\) を作る
3. スライディングウィンドウでサイズ \(K\) の窓のペナルティ合計の最小値を求める
   • 最初の窓 \([0, K-1]\) の合計を計算
   • 窓を1つずつ右にずらすとき、右端を足して左端を引く（\(O(1)\) で更新）
4. 答えは \(\text{total\_positive} - \text{min\_penalty}\)

計算量

• 時間計算量: \(O(N)\)（ペナルティ配列の作成とスライディングウィンドウがそれぞれ \(O(N)\)）
• 空間計算量: \(O(N)\)（配列の保持）

実装のポイント

• \(A_i\) が負の場合のみペナルティが発生するので、\(\max(0, -A_i)\) で正しくペナルティを計算する

• スライディングウィンドウの更新は window_sum += penalties[i+K-1] - penalties[i-1] で \(O(1)\)

• \(A_i\) の絶対値が最大 \(10^9\)、\(N\) が最大 \(5 \times 10^5\) なので、合計値は 64bit 整数の範囲に収まる（Python では自動で多倍長整数になるので問題なし）

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # We must select a subset of flowers to tend, such that there exists at least one
    # contiguous block of K flowers that are all tended. We want to maximize the sum
    # of beauty of tended flowers.
    
    # Strategy: We must include all flowers in some window [l, l+K-1].
    # Additionally, we can include any other flower with positive beauty.
    
    # Total positive = sum of max(0, A[i]) for all i
    # For a window [l, l+K-1], we are forced to include all K flowers in that window.
    # For flowers outside the window, we include them only if A[i] > 0 (already counted in total positive).
    # For flowers inside the window, we must include them even if A[i] < 0.
    
    # So the answer for choosing window starting at l is:
    # total_positive + sum of (A[i] for i in [l, l+K-1] if A[i] < 0)
    # Because negative flowers inside the window are forced, and they weren't in total_positive.
    # Wait, let me reconsider.
    
    # answer(l) = sum_{i in window} A[i] + sum_{i not in window, A[i]>0} A[i]
    #           = sum_{i in window} A[i] + (total_positive - sum_{i in window, A[i]>0} A[i])
    #           = total_positive + sum_{i in window} A[i] - sum_{i in window, A[i]>0} A[i]
    #           = total_positive + sum_{i in window, A[i]<=0} A[i]
    #           = total_positive - sum_{i in window} max(0, -A[i])
    #           = total_positive - (sum of max(0, -A[i]) for i in window)
    
    # So we want to minimize sum of max(0, -A[i]) over a window of size K.
    # That is, minimize the sum of "penalties" (negative values forced to include).
    
    total_positive = 0
    for a in A:
        if a > 0:
            total_positive += a
    
    # penalty[i] = max(0, -A[i])  (this is the cost of being forced to include flower i)
    # We want the window of size K with minimum sum of penalties.
    
    # Compute sliding window sum of penalties
    penalties = [max(0, -a) for a in A]
    
    window_sum = sum(penalties[:K])
    min_penalty = window_sum
    
    for i in range(1, N - K + 1):
        window_sum += penalties[i + K - 1] - penalties[i - 1]
        if window_sum < min_penalty:
            min_penalty = window_sum
    
    print(total_positive - min_penalty)

main()

---

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