概要

スプリンクラーの間隔 \(K\) を \(1 \le K \le N\) から選び、位置 \(1,1+K,1+2K,\ldots\) にある花 o の個数が最大になる値を求めます。

考察

スプリンクラーが水をまくのは、先頭から \(K\) 個おきの区画だけです。つまり（1-indexed で）
$\(1,\ 1+K,\ 1+2K,\ \ldots \le N\)\( にある `o` の数を数えれば、その \)K$ で水やりできる花の数が分かります。

ここで素朴に「各 \(K\) について、全てのマスを見て『この位置は水をまく位置か？』を判定する」と、各 \(K\) に \(O(N)\) かかり全体で \(O(N^2)\) になってしまい、\(N=2\times 10^5\) では間に合いません。

重要な観察は、「水をまく位置だけを直接たどればよい」ということです。
\(K\) を固定したときに見るべき位置は \(1, 1+K, 1+2K, \ldots\) のみで、その個数は約 \(N/K\) 個です。
したがって、各 \(K\) について \(O(N/K)\) で数えられます。

例えば \(N=10, K=3\) なら見る位置は \(1,4,7,10\) の 4 箇所だけで十分です（他の位置は絶対に水をまかないため）。

アルゴリズム

1. 文字列 \(S\) を配列 \(a\) に変換する（o を 1、. を 0 とする）。
2. \(K=1\) から \(N\) まで全探索する。
3. 各 \(K\) について、\(i=0, K, 2K, \ldots\)（0-indexed）を順にたどり、\(a[i]\) を合計する。
   • この合計が「その \(K\) で水やりできる花の数」
4. その最大値を答えとして出力する。

コードでは range(0, N, k) を使うことで、「水をまく位置だけ」を効率よく列挙しています。

計算量

• 時間計算量: \(\displaystyle \sum_{K=1}^{N} O\!\left(\frac{N}{K}\right) = O(N \log N)\)
  （調和級数 \(1+\frac12+\cdots+\frac1N = O(\log N)\) を用いる）
• 空間計算量: \(O(N)\)（o/. を 0/1 にした配列を持つため）

実装のポイント

• 位置は問題文では 1-indexed ですが、Python の配列は 0-indexed なので、先頭（位置 1）をインデックス 0 として 0, k, 2k, ... を見れば一致します。

• S を毎回参照するより、a[i] が 0/1 の配列にしておくと加算が簡単になります。

• 入力が大きいので sys.stdin.readline を使うと安心です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = input().strip()
    a = [1 if c == 'o' else 0 for c in S]

    ans = 0
    for k in range(1, N + 1):
        s = 0
        for i in range(0, N, k):
            s += a[i]
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

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