概要

一列に並んだ花壇に対して、先頭から \(K\) 個おきに水をまくスプリンクラーの間隔 \(K\) を最適に選び、水やりできる花の数を最大化する問題です。

考察

問題の整理

スプリンクラーは位置 \(1, 1+K, 1+2K, \ldots\) に水をまきます。0-indexed で考えると、位置 \(0, K, 2K, 3K, \ldots\) の区画が水やりの対象です。

例えば \(N = 10\)、\(S = \) o.oo.o.oo. の場合： - \(K = 1\)：位置 \(0,1,2,3,4,5,6,7,8,9\) → すべての区画を見るので、花の総数 \(= 5\) - \(K = 3\)：位置 \(0,3,6,9\) → o, o, ., . → 花 \(2\) 個 - \(K = 2\)：位置 \(0,2,4,6,8\) → o, o, ., ., o → 花 \(3\) 個

このように \(K\) の値ごとに水やりされる花の数が変わるため、すべての \(K\) を試して最大値を求めます。

素朴なアプローチの計算量

\(K = 1\) のときは \(N\) 個の区画を調べ、\(K = 2\) のときは \(N/2\) 個、\(K = 3\) のときは \(N/3\) 個、…と調べます。全体の計算量は：

\[\sum_{K=1}^{N} \frac{N}{K} = N \sum_{K=1}^{N} \frac{1}{K} \approx N \ln N\]

これは 調和級数 と呼ばれ、\(O(N \log N)\) になります。\(N = 2 \times 10^5\) のとき約 \(2 \times 10^6\) 程度の演算回数なので、十分高速に動作します。

なぜ全探索で問題ないか

一見すると \(K\) が \(N\) 通りあり、各 \(K\) について最大 \(N\) 個の区画を調べるので \(O(N^2)\) に見えますが、\(K\) が大きいほど調べる区画数が少なくなるため、合計は \(O(N \log N)\) に収まります。

アルゴリズム

1. \(K = 1, 2, \ldots, N\) のそれぞれについて以下を行う：
   • 位置 \(0, K, 2K, 3K, \ldots\)（\(N\) 未満の範囲）を順に調べる
   • その位置の文字が o であれば、カウントを \(1\) 増やす
2. すべての \(K\) に対するカウントの最大値を出力する

計算量

• 時間計算量: \(O(N \log N)\)
  • 調和級数 \(\sum_{K=1}^{N} \lfloor N/K \rfloor = O(N \log N)\) より
• 空間計算量: \(O(N)\)
  • 文字列 \(S\) の保持のみ

実装のポイント

• 問題文では位置が 1-indexed（位置 \(1, 1+K, 1+2K, \ldots\)）ですが、プログラムでは 0-indexed で range(0, N, K) とすることで自然に対応できます。

• Python の range(0, N, K) は \(0, K, 2K, \ldots\) と \(K\) 刻みで \(N\) 未満の値を列挙してくれるので、内側のループが簡潔に書けます。

• 各 \(K\) ごとに count を計算し、これまでの最大値 best と比較して更新するだけのシンプルな実装です。

  ソースコード

import sys

def solve():
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()
    
    best = 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 > best:
            best = count
    
    print(best)

solve()

この解説は claude4.6opus-thinking によって生成されました。