概要

花壇の各区画の状態が与えられ、先頭からK個おきの区画に水をまくとき、水やりできる花の最大数を求める問題です。

考察

問題の条件を素直に実装すると、各K（1からNまで）について、K個おきの区画を調べていくことになります。各Kに対して調べる区画の数は約N/K個なので、全体の計算量はN * (1 + ¹⁄₂ + ¹⁄₃ + … + 1/N) ≈ O(N log N)となります。Nの最大値が2×10^5なので、これは十分に実行可能です。

アルゴリズム

1. 入力として区画数Nと状態文字列Sを受け取る
2. Kを1からNまで変化させながら、それぞれのKについて水やりする区画を調べる
3. 各Kについて、位置0, K, 2K, … の区画が花（’o’）であればカウントする
4. すべてのKの中で最大のカウント値を出力する

計算量

• 時間計算量: \(O(N \log N)\)
  • 各Kについて調べる区画数は約\(N/K\)個で、K=1からNまでの和は調和級数となり\(O(N \log N)\)
• 空間計算量: \(O(N)\)
  • 入力文字列を格納するためのメモリのみ使用

実装のポイント

• whileループを使ってK個おきの位置を効率的に計算する

• インデックスは0から始まることに注意（問題文では位置1から始まるが、プログラムでは0-indexedで処理）

• 各Kについてのカウント値を比較し、最大値を保持する

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    s = data[1]
    
    max_count = 0
    for k in range(1, n + 1):
        count = 0
        i = 0
        while i < n:
            if s[i] == 'o':
                count += 1
            i += k
        if count > max_count:
            max_count = count
            
    print(max_count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。