概要

この問題は、長さ \(N\) の天気列から連続する \(K\) 日間を選び、その中に含まれる晴れの日（S）の最大数を求める問題です。

考察

素朴なアプローチとして、すべての連続する \(K\) 日間の区間について晴れの日数を数える方法が考えられます。しかし、\(N\) の最大値が \(10^6\) であるため、各区間を独立に計算すると \(O(NK)\) の時間がかかり、最悪ケースでは \(10^{12}\) 回の操作が必要となり、実行時間制限に間に合いません。

この問題を効率的に解くためには、隣接する区間の晴れの日数が重複している部分を活用する必要があります。連続する区間は前の区間とほとんど同じで、先頭の1日がなくなり末尾に1日が加わるだけです。この性質を利用すれば、各区間の晴れの日数を定数時間で更新できます。

アルゴリズム

スライディングウィンドウ法を用いて効率的に解きます。具体的な手順は以下の通りです：

1. 左端 left を0、現在の区間の晴れの日数 count を0、最大値 max_count を0で初期化します。
2. 右端 right を0から \(N-1\) まで1つずつ動かします：
   • 現在の日 right が晴れ（S）なら count を1増やします。
   • 現在の区間の長さが \(K\) を超えたら、左端 left の日が晴れなら count を1減らし、left を1増やします。
   • 現在の区間の長さがちょうど \(K\) になったら、max_count を更新します。
3. 最終的に得られた max_count を出力します。

この方法では、各日は最大2回（追加と削除）しか処理されないため、効率的に計算できます。

計算量

• 時間計算量: \(O(N)\)
  • 配列を1回走査するだけです。
• 空間計算量: \(O(N)\)
  • 天気列を保存するための配列が必要です。

実装のポイント

• 区間の長さが \(K\) になるまでは最大値の更新を行わないように注意します。

• 区間の長さが \(K\) を超えた場合のみ左端を動かすことで、常に区間の長さが \(K\) 以下になるように管理します。

• 天気が S かどうかの判定は単純な文字列比較で行います。

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n, k = map(int, data[0].split())
    weathers = data[1].split()
    
    count = 0
    left = 0
    max_count = 0
    
    for right in range(n):
        if weathers[right] == 'S':
            count += 1
            
        if right - left + 1 > k:
            if weathers[left] == 'S':
                count -= 1
            left += 1
            
        if right - left + 1 == k:
            max_count = max(max_count, count)
            
    print(max_count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。