概要

\(N\) 日間の天気情報から、連続する \(K\) 日間を選んで、その中に含まれる「晴れ」の日数を最大化する問題。

考察

この問題では、すべての連続する \(K\) 日間について、「晴れ」の日数を数えてその最大値を求めることになります。

素朴な方法として、すべての区間に対して晴れの日数を数える方法があります。しかし、そのような全探索は \(O(N \cdot K)\) の計算量となり、制約 \(N, K \leq 10^6\) のもとでは時間内に処理しきれません（最大で \(10^{12}\) 回の計算が必要になる）。

そこで登場するのが「スライディングウィンドウ（しゃくとり法の一種）」というテクニックです。
最初の区間 \([0, K-1]\) の晴れの日数を計算したあと、次の区間 \([1, K]\) では、新たに右端に加わる日と左端から外れる日だけを見て、晴れの日数を差分更新していきます。これにより、各区間の計算が \(O(1)\) で行え、全体で \(O(N)\) となります。

たとえば、天気が
S C S R S で \(K=3\) の場合：
- 最初の区間 [S C S] → 晴れは2日
- 次の区間 [C S R] → 左の S が消えて右に R が入るので、晴れの日数は1減って合計1日
- さらに [S R S] → 左の C は関係なく、右に S が入るので1増えて合計2日

このようにして、効率的に最大値を求めることができます。

アルゴリズム

1. 最初の \(K\) 日間における「晴れ」の日数を数える。
2. その後、右にウィンドウを1日ずつスライドさせながら、次のように更新する：
   • 新しく区間に含まれる日が「晴れ」ならカウントを \(+1\)
   • 区間から外れる日が「晴れ」ならカウントを \(-1\)
3. 各ステップで得られたカウントの最大値を記録する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力をリストで保持）

実装のポイント

• 入力の受け取り方によっては 'S' の判定が文字列比較になるので注意（スペース区切りで読み込む場合はリストにする）

• 最初の区間の晴れの日数を正しく計算することが重要

• スライドさせる際に、インデックスエラーにならないよう範囲に注意

  ソースコード

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)

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