概要

一列に並んだ花壇に対し、等間隔で水をまいて多くの花に水が届くようにするときの最大値を求める問題です。

考察

この問題では、スプリンクラーの間隔 \(K\) を \(1\) から \(N\) まで全て試して、それぞれの場合について水をまける花の数を数えるのが自然なアプローチです。

例えば、\(S = "o.o.o"\)、つまり花が位置1, 3, 5にある場合を考えます。

• \(K=1\) のとき、位置 \(1, 2, 3, 4, 5\) すべてに水が行き、花は3本が水を受ける。
• \(K=2\) のとき、位置 \(1, 3, 5\) に水が行き、花は3本が水を受ける。
• \(K=3\) のとき、位置 \(1, 4\) に水が行き、花は1本が水を受ける。

このように、\(K\) を全探索することで最大値を求めることができます。

素朴な全探索でも、制約 \(N \leq 2 \times 10^5\) に対して各 \(K\) で最大 \(N\) 回のチェックが必要なので、全体で最大 \(N^2 = 4 \times 10^{10}\) 回の操作が必要になり、これは時間制限（通常1秒程度）を超えてしまいます。

しかし、実際には \(K\) が大きくなるにつれて調べる回数（\(N/K\)）が減っていくため、計算量は \(O(N \log N)\) 程度に抑えられます。これは十分高速です。

アルゴリズム

1. 各 \(K = 1, 2, ..., N\) に対して以下を行う：
   • 位置 \(0, K, 2K, 3K, ...\) （Pythonのインデックスでは \(0\) スタート）の区画に水をまき、そこに花（o）があればカウントする。
2. カウントの最大値を記録していく。
3. 最終的に得られた最大値を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  　→ 各 \(K\) について調べる要素数が \(N/K\) 個あり、合計で \(\sum_{K=1}^{N} \frac{N}{K} \approx N \log N\)
• 空間計算量: \(O(1)\)
  　→ 入力を除けば定数個の変数のみ使用

実装のポイント

• 文字列のインデックスは0始まりだが、問題文の「位置」は1始まりなので注意（が、コード上は0始まりで統一すれば問題ない）
• 入力の読み取りを高速に行うために sys.stdin.read を使う
• 各 \(K\) に対して、range(0, N, K) を使って等間隔の位置を取得するとシンプルに書ける

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = data[1]
    
    max_watered = 0
    
    for K in range(1, N + 1):
        count = 0
        for i in range(0, N, K):
            if S[i] == 'o':
                count += 1
        if count > max_watered:
            max_watered = count
            
    print(max_watered)

if __name__ == "__main__":
    main()

---

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