概要

\(N\) 日間の天気予報が与えられたとき、連続する \(K\) 日間を選んで、その中に含まれる晴れの日数を最大化する問題です。スライディングウィンドウ（尺取り法）を用いて効率的に解くことができます。

考察

素朴なアプローチとその問題点

最も単純な方法は、すべての開始日 \(d\)（\(1 \leq d \leq N - K + 1\)）について、\(d\) 日目から \(d + K - 1\) 日目までの晴れの日数をそれぞれ数えることです。

• 開始日の候補は \(N - K + 1\) 通り
• 各候補について \(K\) 日分を数える

この場合、計算量は \(O((N - K + 1) \times K)\) となり、最悪で \(O(N^2)\) 程度になります。\(N\) が最大 \(10^6\) のため、\(10^{12}\) 回程度の操作が必要になり、TLE（時間超過） になってしまいます。

重要な気づき

連続する \(K\) 日間のウィンドウを 1 日ずらしたとき、変化するのは 左端から 1 日が抜ける ことと 右端に 1 日が加わる ことだけです。

例えば \(N = 7, K = 3\) で天気が S C S S R S C の場合：

ウィンドウ	日	晴れの数	変化
1〜3日目	S C S	2	初期値
2〜4日目	C S S	2	1日目の S が抜け、4日目の S が入る
3〜5日目	S S R	2	2日目の C が抜け、5日目の R が入る

このように、前の区間の晴れの数から 差分だけを更新 すれば、各ステップ \(O(1)\) で計算できます。

アルゴリズム

スライディングウィンドウ（固定長の区間を 1 つずつスライドさせる手法）を用います。

1. 各日の天気を、晴れなら \(1\)、それ以外なら \(0\) に変換した配列 sunny を作る。
2. 最初のウィンドウ（1 日目〜\(K\) 日目）の晴れの日数 current を計算する。
3. ウィンドウを 1 日ずつ右にスライドさせる：
   • 新しく右端に入る日の値 sunny[i] を加算する。
   • 左端から出る日の値 sunny[i - K] を減算する。
   • current が今までの最大値 best を超えたら更新する。
4. 最終的な best が答え。

current += sunny[i] - sunny[i - K]

このたった 1 行の更新で、ウィンドウ内の晴れの日数を常に正しく保てるのがポイントです。

計算量

• 時間計算量: \(O(N)\) — 配列の作成に \(O(N)\)、スライディングウィンドウの走査に \(O(N)\)
• 空間計算量: \(O(N)\) — 天気を 0/1 に変換した配列 sunny の分

\(N = 10^6\) でも十分高速に動作します。

実装のポイント

• 天気文字列をあらかじめ 1/0 の整数配列に変換しておくと、ウィンドウの更新が単純な加減算になり、コードが簡潔になります。

• 最初のウィンドウの合計を sum(sunny[:K]) で求め、それ以降はループで差分更新する、という 2 段階の構成にするとバグが起きにくくなります。

• if current > best の比較を max(best, current) ではなく直接比較にしているのは、関数呼び出しのオーバーヘッドを避けて高速化するためです（\(N\) が大きい場合に効果があります）。

  ソースコード

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

sunny = [1 if w == 'S' else 0 for w in W]

current = sum(sunny[:K])
best = current

for i in range(K, N):
    current += sunny[i] - sunny[i - K]
    if current > best:
        best = current

print(best)

---

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