問題概要

o と x のみからなる長さ $N$ の文字列 $S$ が与えられる。

文字列 $S$ を $M$ 回繰り返して得られる文字列 $T$ を考える。この文字列 $T$ に対して、最大 $K$ 回まで、x を o に書き換える操作を行うことができる。

書き換えた後の、o が連続する部分文字列の長さとして、考えられる最大値を求めよ。

制約

$1 \le N \le 3 \times 10^{5}$
$1 \le M \le 10^{9}$

考えたこと

文字列 $T$ 上の区間 $\lbrack l, r)$ であって、その区間内の x の個数が $K$ 個以下であるときの、 $r-l$ の最大値を求める問題と言える。

$l$ を固定して考えることにした。ここで、 $l = 0, 1, \dots, N-1$ の場合のみ考えれば十分である。

$l$ を固定すると、次のような問題と言える。

文字列 $T$ の区間 $\lbrack l, r)$ 内の x の個数が $K$ 個以下となるような最大の $r$ を求めよ

これは二分探索法によって $O(\log N + \log M)$ の計算量で求められる。

よって、全体として $O(N(\log N + \log M))$ の計算量で解ける。

AC したコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M, K;
    string S;
    cin >> N >> M >> K >> S;
    
    // S の中の x の個数を高速に求めるための累積和
    vector<long long> sum(N + 1, 0);
    for (int i = 0; i < N; ++i) sum[i+1] = sum[i] + (S[i] == 'x');
    
    // T の len 文字目から考えるか場合を全探索 (len = 0, 1, ..., N-1)
    long long res = 1;
    for (int len = 0; len < N; ++len) {
        // T の [len, len+x) 中の x の個数が K 個以下となる最大の x を求める
        long long left = -1, right = N * M - len + 1;
        while (right - left > 1) {
            long long x = (left + right) / 2;
            
            long long kurikaeshi = (x + len) / N;
            long long amari = (x + len) % N;
            long long num = sum.back() * kurikaeshi + sum[amari] - sum[len];
            
            if (num <= K) left = x;
            else right = x;
        }
        res = max(res, left);
    }
    cout << res << endl;
}