ARC 140

Table of Contents

A. Right String

https://atcoder.jp/contests/arc140/tasks/arc140_a

解説 AC。

答えが $N$ の約数のいずれかになることまではわかったが最終的な答えの求め方を間違えた。

$d|N$ となる $d$ について考える。$S$ を下記のように $d$ 個ずつに分割する。

12$\cdots$d
$S_1$$S_2$$\cdots$$S_d$
$S_{d+1}$$S_{d+2}$$\cdots$$S_{2d}$
$\vdots$$\vdots$$\ddots$$\vdots$
$S_{N-d+1}$$S_{N-d+2}$$\cdots$$S_N$

列 $i$ に対して最頻出文字に全ての文字を置き換えるのに必要な操作回数を $c_i$ とすると $\sum_i c_i \leq K$ のとき題意の操作を実行してできる文字種は $d$ になる。よって $f(S) \leq d$. 同様に全ての $N$ の約数について調べ $f(S) \leq d$ を達成できる最小の $d$ が答え。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    string s;
    cin >> n >> k >> s;

    ll ans = n;
    rep2(d, 1, n) {
        if (n % d)
            continue;

        int sum = 0;
        rep(i, d) {
            vint cnt(26, 0);
            for (int j = i; j < n; j += d) {
                cnt[s[j] - 'a']++;
            }
            sum += *max_element(all(cnt));
        }
        if (n - sum <= k)
            chmin(ans, d);
    }
    cout << ans << endl;
}