概要

\(N\) 個の花壇から、「連続する \(K\) 個以上の区間を少なくとも 1 つ含む」という条件を満たしつつ、選んだ花壇の美しさの合計を最大化する問題です。

考察

1. 自由度を考える

もし「連続する \(K\) 個」という制約がなければ、美しさが正である花壇（\(A_i > 0\)）をすべて選び、負である花壇は選ばないのが最適です。 しかし、この問題では「どこか 1 箇所は必ず連続して \(K\) 個選ばなければならない」という制約があります。

2. 選ぶ花壇を固定して考える

ある連続する \(K\) 個の区間 \(W\)（花壇 \(l, l+1, \ldots, l+K-1\)）をすべて手入れすることに決めたとします。このとき、合計値を最大化するには、区間 \(W\) 以外の花壇については以下のように選ぶのが最善です。 - 美しさ \(A_i\) が正なら、手入れする。 - 美しさ \(A_i\) が負または 0 なら、手入れしない。

3. 数式の整理

全花壇のうち、美しさが正であるものの合計を \(S\) とします（\(S = \sum_{A_i > 0} A_i\)）。 特定の区間 \(W\) を選んだときの合計値は、次のように表せます。 $\(\text{合計値} = (\text{区間 } W \text{ に含まれる } A_i \text{ の総和}) + (\text{区間 } W \text{ に含まれない正の } A_i \text{ の総和})\)$

ここで、後者の「区間 \(W\) に含まれない正の \(A_i\) の総和」は、\(S - (\text{区間 } W \text{ に含まれる正の } A_i \text{ の総和})\) と書き換えられます。 これを用いると、 $\(\text{合計値} = (\text{区間 } W \text{ の総和}) + S - (\text{区間 } W \text{ に含まれる正の } A_i \text{ の総和})\)\( \)\(\text{合計値} = S + (\text{区間 } W \text{ に含まれる負または 0 の } A_i \text{ の総和})\)$ となります。

\(S\) は固定の値なので、合計値を最大化するためには、「区間 \(W\) に含まれる \(A_i \leq 0\) である要素の和」を最大化すればよいことがわかります。

アルゴリズム

1. 正の要素の総和を計算: 配列 \(A\) のうち、\(A_i > 0\) であるものの総和 \(S\) を求めます。
2. 変換した配列の作成: 各要素 \(A_i\) に対して、以下のルールで新しい値 \(C_i\) を決めます。
   • \(A_i \leq 0\) のとき：\(C_i = A_i\)
   • \(A_i > 0\) のとき：\(C_i = 0\)
3. スライディングウィンドウ: 配列 \(C\) の中で、長さ \(K\) の連続する区間の和の最大値を求めます。
   • 最初の \(K\) 個の和を計算し、その後は「右端を足して左端を引く」操作を繰り返すことで、すべての区間の和を \(O(N)\) で計算できます。
4. 答えの出力: \(S + (\text{区間和の最大値})\) が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • 配列の走査とスライディングウィンドウによる計算がそれぞれ \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 入力値および変換した配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(A_i\) の値が負である場合、区間和の最大値も 0 以下になります。例えば \(A = [-10, -5, -10], K=2\) の場合、区間和の最大値は \(-15\) となります。

• 合計値が非常に大きな（または小さな）値になる可能性があるため、プログラミング言語によっては 64bit 整数型（Python では標準の int）を使用するように注意してください。

  ソースコード

import sys

def solve():
    # Read all input from standard input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        # N: Total number of flowerbeds
        # K: Required length of consecutive maintained flowerbeds
        N = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    
    # A: List of beauty values for each flowerbed
    A = list(map(int, it))
    
    # The condition is that there must be at least one consecutive block of 
    # K flowerbeds that are all maintained. To maximize the total beauty sum, 
    # if we choose a specific block W of length K to satisfy the condition, 
    # we should also maintain any other flowerbed outside of W if its beauty 
    # is positive.
    #
    # Let S be the sum of all positive beauty values in the entire array A.
    # The total beauty sum for a chosen block W is:
    #   Total = sum(A[i] for i in W) + sum(A[i] for i not in W if A[i] > 0)
    #
    # This can be rewritten using S:
    #   Total = sum(A[i] for i in W) + (S - sum(A[i] for i in W if A[i] > 0))
    #   Total = S + (sum(A[i] for i in W) - sum(A[i] for i in W if A[i] > 0))
    #   Total = S + sum(A[i] for i in W if A[i] <= 0)
    #
    # Thus, the problem reduces to finding a window W of size K that maximizes 
    # the sum of non-positive beauty values (min(0, A_i)).
    
    S = 0
    C = [0] * N
    for i in range(N):
        val = A[i]
        if val > 0:
            S += val
        else:
            # If A[i] is 0 or negative, its contribution to the window is itself.
            # If A[i] is positive, its contribution to the window sum adjustment is 0.
            C[i] = val
            
    # We no longer need the original array A, so we can free up memory.
    del A
    
    # Use a sliding window to find the maximum sum of K consecutive elements in C.
    # Since all elements in C are <= 0, we are looking for the window with the 
    # "least negative" sum.
    
    # Initial window sum for the first block of size K
    curr_window_sum = sum(C[:K])
    max_window_sum = curr_window_sum
    
    # Slide the window across the array C from left to right.
    # There are N - K + 1 possible windows in total.
    for i in range(N - K):
        # Update the window sum by removing the leftmost element and adding the new rightmost element.
        curr_window_sum = curr_window_sum - C[i] + C[i + K]
        if curr_window_sum > max_window_sum:
            max_window_sum = curr_window_sum
            
    # The maximum possible beauty sum is the sum of all positives plus the 
    # maximum window adjustment.
    print(S + max_window_sum)

if __name__ == '__main__':
    solve()

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