概要

\(N\) 個の区画からなる花壇に対し、スプリンクラーの間隔 \(K\) （\(1 \le K \le N\)）を適切に選ぶことで、インデックス \(0, K, 2K, \dots\) （0-indexed）にある花の数（o の数）を最大化する問題です。

考察

1. 問題の言い換え

スプリンクラーが水をまく位置は、1-indexed では \(1, 1+K, 1+2K, \dots\) ですが、プログラミングで一般的な 0-indexed（配列の添字が 0 から始まる形式）に直すと、インデックス \(0, K, 2K, \dots\) となります。 つまり、文字列 \(S\) の \(0\) 番目から始めて \(K\) おきに文字を確認し、そこに含まれる o の個数を数えればよいことになります。

2. 素朴な全探索の検討

\(K\) を \(1\) から \(N\) まで全て試すことを考えます。 - \(K=1\) のとき：\(0, 1, 2, 3, \dots\) 番目を確認（約 \(N\) 回） - \(K=2\) のとき：\(0, 2, 4, 6, \dots\) 番目を確認（約 \(N/2\) 回） - \(K=3\) のとき：\(0, 3, 6, 9, \dots\) 番目を確認（約 \(N/3\) 回） - … - \(K=N\) のとき：\(0\) 番目のみ確認（\(1\) 回）

このときの合計の計算回数は、以下の式のようになります。 $\(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)\)$

括弧の中身は「調和級数」と呼ばれ、その和はおよそ \(\ln N\)（自然対数）になることが知られています。したがって、全体の計算量は \(O(N \log N)\) となります。

3. 制約の確認

\(N = 2 \times 10^5\) のとき、\(N \log N\) はおよそ \(2.4 \times 10^6\) 程度です。一般的な競技プログラミングの制限時間（2秒）では、\(10^7\) 〜 \(10^8\) 回程度の計算が可能であるため、この全探索の解法で十分に間に合うと判断できます。

アルゴリズム

1. 花の最大数 max_flowers を 0 で初期化する。
2. \(K\) を \(1\) から \(N\) まで \(1\) ずつ増やしながら以下の処理を繰り返す：
   • 文字列 \(S\) から、インデックス \(0, K, 2K, \dots\) にある文字を抽出する。
   • 抽出した文字の中にある o の個数を数える。
   • 数えた個数が max_flowers より大きければ、max_flowers を更新する。
3. 最終的な max_flowers を出力する。

計算量

• 時間計算量: \(O(N \log N)\) 前述の通り、調和級数の性質により \(K\) ごとの処理回数の合計が \(O(N \log N)\) に収まります。
• 空間計算量: \(O(N)\) 入力文字列 \(S\) を保持するためのメモリが必要です。

実装のポイント

Python では、スライス機能 S[::K] を使うことで、インデックス \(0, K, 2K, \dots\) の要素を非常に高速に抽出できます。 また、抽出された部分文字列に対して .count('o') メソッドを適用することで、ループを自分で書くよりも簡潔かつ高速に o の数をカウントできます。

ソースコード

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()

---

この解説は gemini-3-flash-thinking によって生成されました。