Overview

Given weather information for \(N\) days, select a consecutive \(K\)-day period to maximize the number of “sunny” days within it.

Analysis

In this problem, we need to count the number of “sunny” days for every consecutive \(K\)-day period and find the maximum value.

A naive approach would be to count the number of sunny days for every such interval. However, this brute-force method has a time complexity of \(O(N \cdot K)\), which is too slow under the constraints \(N, K \leq 10^6\) (requiring up to \(10^{12}\) operations).

This is where the “sliding window” technique (a type of two-pointer method) comes in. After computing the number of sunny days in the first interval \([0, K-1]\), for the next interval \([1, K]\), we only need to look at the day newly added on the right end and the day removed from the left end, updating the sunny day count incrementally. This allows each interval’s computation to be done in \(O(1)\), resulting in an overall complexity of \(O(N)\).

For example, if the weather is S C S R S with \(K=3\): - First interval [S C S] → 2 sunny days - Next interval [C S R] → The S on the left is removed and R is added on the right, so the sunny day count decreases by 1, totaling 1 day - Then [S R S] → The C on the left doesn’t affect the count, and S is added on the right, so it increases by 1, totaling 2 days

In this way, we can efficiently find the maximum value.

Algorithm

1. Count the number of “sunny” days in the first \(K\) days.
2. Then, slide the window one day to the right at a time, updating as follows:
   • If the newly included day is “sunny”, increment the count by \(+1\)
   • If the day leaving the interval is “sunny”, decrement the count by \(-1\)
3. Record the maximum count obtained at each step.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (storing the input as a list)

Implementation Notes

• Depending on how input is read, checking for 'S' may involve string comparison, so be careful (if reading with space-separated input, convert to a list)

• It is important to correctly compute the number of sunny days in the initial interval

• When sliding the window, be careful with index ranges to avoid index-out-of-bounds errors

  Source Code

N, K = map(int, input().split())
W = list(input().split())

# 最初のK日間の晴れの日数を計算
current_sunny = sum(1 for i in range(K) if W[i] == 'S')
max_sunny = current_sunny

# スライディングウィンドウで次の区間の晴れの日数を計算
for i in range(K, N):
    # 新しく加わる日が晴れなら+1
    if W[i] == 'S':
        current_sunny += 1
    # 範囲から外れる日が晴れなら-1
    if W[i - K] == 'S':
        current_sunny -= 1
    # 最大値を更新
    max_sunny = max(max_sunny, current_sunny)

print(max_sunny)

This editorial was generated by qwen3-coder-480b.