概要

長さ \(K\) の連続区間を 1 つ選んだとき、その区間に含まれる「晴れ（S）」の日数の最大値を求めます。

考察

各区間（\(d\) 日目〜\(d+K-1\) 日目）の「晴れの日数」を数えて最大を取ればよいですが、区間は全部で \(N-K+1\) 個あります。

• 素朴な方法: 各区間ごとに \(K\) 日を数え直す
  → 計算量が \(O((N-K+1)\times K) \approx O(NK)\) になり、\(N,K \le 10^6\) では最大で \(10^{12}\) 回程度の処理になって間に合いません（TLE）。

ここで重要な観察は、隣り合う区間はほとんど重なっていることです。

例：\(K=3\) のとき
- 区間 \([1,3]\) の次は \([2,4]\)
→ 共通部分は \([2,3]\) なので、変わるのは「抜ける 1 日」と「入る 1 日」だけです。
つまり、毎回 \(K\) 個を数え直す必要はなく、前の区間の結果から 差分更新できます。

アルゴリズム

スライディングウィンドウ（尺取りの定番）で解きます。

1. 各日について、晴れなら \(1\)、それ以外（C,R）なら \(0\) に変換した配列 arr を作る。
2. 最初の \(K\) 日（\([0, K-1]\)）の合計 s を計算し、これを暫定最大 best とする。
3. 区間を 1 日ずつ右にずらしながら次を繰り返す（\(i = K, K+1, ..., N-1\)）:
   • 新しく入る日 arr[i] を足す
   • 左端から抜ける日 arr[i-K] を引く
     つまり s += arr[i] - arr[i-K]
   • best = max(best, s) を更新する
4. best を出力する。

この方法なら、各日を定数回しか処理しないため高速です。

計算量

• 時間計算量: \(O(N)\)
  （最初の和の計算 \(O(K)\) と、スライド更新 \(O(N-K)\) の合計で結局 \(O(N)\)）
• 空間計算量: \(O(N)\)
  （晴れかどうかを 0/1 で保持する配列 arr の分）

実装のポイント

• \(N \le 10^6\) なので、Python では入力がボトルネックになりがちです。提出コードでは sys.stdin.buffer.read() で一括読み込みし、空白をスキップしながら高速にパースしています。

• 天気は文字列ですが、S かどうかだけ分かればよいので、'S' を バイト値 83 と比較して 1/0 に変換しています（arr[i] = 1 if c == 83 else 0）。

• スライディングウィンドウでは「入る要素を足す」「出る要素を引く」を間違えないことが重要です（arr[i] - arr[i-K]）。

  ソースコード

import sys

data = sys.stdin.buffer.read()
L = len(data)
p = 0

def skip():
    global p
    while p < L and data[p] <= 32:
        p += 1

def read_int():
    global p
    skip()
    x = 0
    while p < L and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = read_int()
K = read_int()

arr = bytearray(N)
for i in range(N):
    skip()
    c = data[p]
    arr[i] = 1 if c == 83 else 0  # 'S' == 83
    p += 1
    while p < L and data[p] > 32:
        p += 1

s = 0
for i in range(K):
    s += arr[i]
best = s

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

sys.stdout.write(str(best))

この解説は gpt-5.2-high によって生成されました。