Overview

Given a flower bed consisting of \(N\) sections, the problem asks to appropriately choose a sprinkler interval \(K\) (\(1 \le K \le N\)) to maximize the number of flowers (count of o) at indices \(0, K, 2K, \dots\) (0-indexed).

Analysis

1. Restating the Problem

The positions where the sprinkler waters are \(1, 1+K, 1+2K, \dots\) in 1-indexed notation, but converting to 0-indexed (where array indices start from 0), which is common in programming, they become indices \(0, K, 2K, \dots\). In other words, starting from position \(0\) of string \(S\), we check every \(K\)-th character and count the number of o characters contained there.

2. Considering a Naive Brute Force

Let us consider trying all values of \(K\) from \(1\) to \(N\). - When \(K=1\): check positions \(0, 1, 2, 3, \dots\) (approximately \(N\) times) - When \(K=2\): check positions \(0, 2, 4, 6, \dots\) (approximately \(N/2\) times) - When \(K=3\): check positions \(0, 3, 6, 9, \dots\) (approximately \(N/3\) times) - … - When \(K=N\): check only position \(0\) (\(1\) time)

The total number of computations in this case is given by the following expression: $\(N + \frac{N}{2} + \frac{N}{3} + \dots + \frac{N}{N} = N \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{N} \right)\)$

The content inside the parentheses is known as the “harmonic series,” and its sum is known to be approximately \(\ln N\) (natural logarithm). Therefore, the overall time complexity is \(O(N \log N)\).

3. Checking the Constraints

When \(N = 2 \times 10^5\), \(N \log N\) is approximately \(2.4 \times 10^6\). Under typical competitive programming time limits (2 seconds), roughly \(10^7\) to \(10^8\) computations are feasible, so we can conclude that this brute force approach is sufficiently fast.

Algorithm

1. Initialize the maximum number of flowers max_flowers to 0.
2. Iterate \(K\) from \(1\) to \(N\), incrementing by \(1\), and repeat the following:
   • From string \(S\), extract characters at indices \(0, K, 2K, \dots\).
   • Count the number of o characters among the extracted characters.
   • If the counted number is greater than max_flowers, update max_flowers.
3. Output the final max_flowers.

Complexity

• Time Complexity: \(O(N \log N)\) As described above, due to the properties of the harmonic series, the total number of operations across all values of \(K\) is bounded by \(O(N \log N)\).
• Space Complexity: \(O(N)\) Memory is needed to store the input string \(S\).

Implementation Notes

In Python, by using the slice feature S[::K], elements at indices \(0, K, 2K, \dots\) can be extracted very efficiently. Additionally, by applying the .count('o') method to the extracted substring, the count of o can be computed more concisely and efficiently than writing a loop manually.

Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストに格納します。
    # N は花壇の区画数、S は花壇の状態を表す文字列です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    s = input_data[1]
    
    max_flowers = 0
    
    # スプリンクラーの設定値 K は 1 以上 N 以下の整数です。
    # 水をまく位置は 1, 1+K, 1+2K, ... ですが、これは 0-indexed の文字列 S において
    # インデックス 0, K, 2K, ... に相当します。
    # Python のスライス機能 S[::K] を使うことで、これらの位置にある文字を効率的に抽出できます。
    
    # 各 K に対して、抽出された文字列中の 'o' (花) の個数をカウントします。
    # 全体の計算量は O(N/1 + N/2 + N/3 + ... + N/N) = O(N log N) となり、
    # N = 2 * 10^5 の制約下でも十分に高速に動作します。
    for k in range(1, n + 1):
        # S[::k] で抽出された部分文字列内で 'o' が出現する回数を数えます。
        current_count = s[::k].count('o')
        if current_count > max_flowers:
            max_flowers = current_count
            
    # 最大値を標準出力に書き出します。
    sys.stdout.write(str(max_flowers) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.