\(S\) における ATCODER の出現位置は重なりません。よって、\(S\) を ATCODER が出現する位置で分解したとき、一意に定まります。

つまり、 \(S\) は (ATCODER ではない文字列)+ATCODER+(ATCODER ではない文字列)+\(\ldots\) となります。 ここで、隣接しているATCODER 同士をつなげて一つの区間と考えて、\(S\) を (ATCODER ではない文字列)+ATCODERの区間+\(\ldots\) と分解します。

基本的に左右にATCODERではない文字列があるようなATCODER の区間は \(k\) 個の ATCODER があるとき、\(l\) 回 \((l \leq k+1)\) で \(l\) 個のATCODER が得られます。 ただし、片方が端のとき、そもそも \(S\) 全体が ATCODER を複数個連結したものであるときなどは別途の場合分けが必要です。

\(S\) 全体が ATCODER を複数個連結したものであるとき、\(k\) 個の ATCODER が含まれるのであれば、\(M\geq k-1\) で答えは \(k\) 、それ以外では \(M\) が答えになります。

\(S\) に ATCODER 以外の文字列があるとします。まず、両端に ATCODER がある間は端から取って行くのが最適です。このとき \(a\) 回切るだけで \(a\) 個の ATCODER が得られます。 その後、残っている ATCODER はすべて両端に関係ない文字列が存在します。このとき、ATCODER が連続する個数が多い区間から貪欲にそれぞれの区間について切っていくのが最適です。このことは連続する個数が多い方をより初めに持ってきても損しないことから言えます。これを合計 \(K\) 回切り終わる、あるいはすべての ATCODER が切断されるまで繰り返します。

ソートがボトルネックとなり、 時間計算量 \(\mathrm{O}(N \log N)\) となります。(適切な実装ではソートも含めて \(\mathrm{O}(N)\) にすることもできます。)

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<pair<int, int>> atcoders;
    for (int i = 0; i + 7 <= n; ++i) {
        if (s.substr(i, 7) == "ATCODER") {
            if (!atcoders.empty() && atcoders.back().second == i)
                atcoders.back().second = i + 7;
            else
                atcoders.emplace_back(i, i + 7);
            i += 6;
        }
    }
    if (atcoders.empty()) {
        cout << 0 << endl;
        return 0;
    }
    if (atcoders.size() == 1 && atcoders.back() == pair<int, int>{0, n}) {
        if (m >= n / 7 - 1) {
            cout << n / 7 << endl;
        } else
            cout << m << endl;
        return 0;
    }
    vector<int> middle;
    for (auto [l, r] : atcoders) {
        if (l != 0 && r != n) {
            middle.emplace_back((r - l) / 7);
        }
    }
    sort(middle.rbegin(), middle.rend());
    int cnt = 0;
    if (atcoders.front().first == 0) cnt += (atcoders.front().second - atcoders.front().first) / 7;
    if (atcoders.back().second == n) cnt += (atcoders.back().second - atcoders.back().first) / 7;
    int ans = 0;
    ans += min(m, cnt);
    m -= ans;
    for (auto e : middle) {
        if (m <= 1) break;
        ans += min(e, m - 1);
        m -= min(e, m - 1) + 1;
    }
    cout << ans << endl;
}