概要

ATCODER の出現位置を全部調べ、隣り合って連続している出現をひとまとめにして考えると、各まとまりから何個の当たり断片を作るのに何回切断が必要かがきれいに整理できます。
あとは「切断 1 回で増やせる個数」と「中間のまとまりを使うための初期コスト」を数える問題に落とせます。

考察

まず、当たり断片は文字列 ATCODER と 完全一致 する必要があります。
したがって、候補になるのは \(S\) の中に現れる ATCODER の出現箇所だけです。

1. ATCODER の出現は重ならない

ATCODER には、「真の接頭辞 = 真の接尾辞」になるものがありません。
そのため、2 つの ATCODER が途中で重なることはありません。

例えば長さを \(L=8\) とすると、もし 2 個の出現が重なるなら、ある \(1 \le d < L\) について

• 先頭側の長さ \(L-d\) の接尾辞
• 後ろ側の長さ \(L-d\) の接頭辞

が一致するはずですが、ATCODER ではそれが起きません。

よって、出現位置は

• 離れている
• ちょうど隣り合っている（開始位置の差が \(8\)）

のどちらかです。

---

2. 素朴な方法が厳しい理由

例えば

• 「どこで切るか」を全部試す
• DP で「何文字目まで見て、何回切ったか」を持つ

のような方法を考えると、\(N \le 10^6\) なので到底間に合いません。
\(O(NM)\) のような計算量は不可能です。

そこで、ATCODER の出現のしかたに注目して、もっと強く整理します。

---

3. 連続した出現を 1 つのブロックとしてまとめる

ATCODER が隙間なく並んでいる部分を 1 つのブロックとして扱います。

例えば

• ATCODERATCODERATCODER は長さ 3 のブロック
• 間に別の文字が入れば別ブロック

です。

以後、1 ブロックに ATCODER が \(c\) 個連続しているとします。

---

4. 1 ブロックから \(x\) 個取り出すのに必要な切断回数

ここがこの問題の本質です。

左端または右端に接しているブロック

例えば先頭から ATCODERATCODER... と並んでいるなら、先頭から \(x\) 個を取るのが最も得です。

• \(x\) 個の ATCODER を \(x\) 個の断片として取り出すには
• ブロック内部の境界を \(x-1\) 回切り
• 最後に残りと分けるために 1 回切る

ので、必要な切断回数は \(x\) 回 です。

つまり、端のブロックでは
「当たり断片 1 個につき切断 1 回」
で増やせます。

---

両端に接していない（中間の）ブロック

中間にあるブロックから \(x\) 個取り出すには、

• 左側と切り離す 1 回
• 右側と切り離す 1 回
• ブロック内部を \(x-1\) 回切る

ので、合計 \(x+1\) 回 です。

つまり中間ブロックは

• 使い始めるのに追加で 1 回必要
• その後は 1 個増やすごとに 1 回

と考えられます。
この「最初の 1 回」を 起動コスト とみなせます。

---

5. 何を選べば最適か

端のブロックたちに含まれる ATCODER の総数を free_cap とします。
これは「起動コストなしで 1 個 1 切断で取れる個数」です。

一方、中間ブロックの個数をそれぞれ \(c_1, c_2, \dots\) とします。

中間ブロックを \(a\) 個使うと決めた場合

その \(a\) 個のブロックを使うために、まず起動コストとして \(a\) 回 切断が必要です。
残りの \(M-a\) 回の切断で、当たり断片を 1 個ずつ増やせます。

したがって、作れる当たり断片数は

• 残り切断回数の上限：\(M-a\)
• そもそも存在する個数の上限：free_cap + 選んだ a 個のブロックの個数合計

の小さい方です。

つまり

\[ \text{answer}(a)=\min\left(M-a,\ \text{free\_cap}+\sum(\text{選んだ }a\text{ 個のブロックの大きさ})\right) \]

となります。

ここで、固定した \(a\) に対しては、使う中間ブロックは 大きいものから \(a\) 個選ぶ のが最善です。
なので、中間ブロックの大きさを降順にソートし、累積和を取ればよいです。

---

6. 例外：文字列全体が ATCODER の繰り返し

例えば

• ATCODERATCODER

のように、文字列全体が 1 つの連続ブロックになっている場合は少し特殊です。

このとき全部を ATCODER に分けるには、外側を切る必要がないので、

• ATCODER が \(c\) 個あるなら
• 必要な切断は \(c-1\) 回

です。

これは通常の「1 個につき 1 回」より 1 回得です。
例えば 2 個並んでいれば、真ん中を 1 回切るだけで 2 個とも当たり断片にできます。

そのため、このケースだけ最後に特別扱いします。

アルゴリズム

1. T = "ATCODER" とし、長さ \(8\) のすべての部分文字列を調べて、T の出現開始位置を列挙する。
2. 開始位置の差がちょうど \(8\) のものをつなげて、「連続出現ブロック」にまとめる。
   各ブロックを (開始位置, 個数) で持つ。
3. 各ブロックについて
   • 左端に接する先頭ブロックなら free_cap に個数を足す
   • 右端に接する末尾ブロックなら free_cap に個数を足す
   • それ以外は中間ブロックとして個数を配列 middle に入れる
4. middle を降順ソートし、累積和 pref を作る。
5. 中間ブロックを \(a\) 個使うとして、\(a=0,1,\dots,\min(|middle|,\lfloor M/2 \rfloor)\) を全探索する。
   • 容量 cap = free_cap + pref[a]
   • 作れる個数 min(M - a, cap) を計算し、最大値を更新する。
6. さらに、「文字列全体が 1 つの連続ブロック」で、ATCODER が \(c\) 個並んでいる場合、\(M \ge c-1\) なら答えを少なくとも \(c\) にできるので反映する。

計算量

• 時間計算量: \(O(N + K \log K)\)
• 空間計算量: \(O(K)\)

ここで \(K\) は ATCODER の出現ブロック数です。
ATCODER の長さは固定で \(8\) なので、出現探索は実質 \(O(N)\) です。

実装のポイント

• ATCODER の長さは固定なので、各位置で S[i:i+8] == "ATCODER" を調べても全体で \(O(N)\) です。

• ATCODER は重ならないため、出現位置をそのまま左から見て「差が 8 かどうか」でブロック化できます。

• 中間ブロックを \(a\) 個使うには、最低でも各ブロック 1 個は取らないと意味がないので、\(a \le M/2\) まで見れば十分です。

• 「文字列全体が ATCODER の繰り返し」のケースだけは、両端の切断が不要になるため別処理が必要です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().strip()

    T = "ATCODER"
    L = len(T)

    # "ATCODER" has no proper prefix that is also a suffix,
    # so its occurrences in S never overlap.
    pos = []
    for i in range(N - L + 1):
        if S[i:i + L] == T:
            pos.append(i)

    if not pos:
        print(0)
        return

    # Group consecutive occurrences with gap exactly L into runs.
    runs = []  # (start_position, count)
    for p in pos:
        if not runs or p != runs[-1][0] + runs[-1][1] * L:
            runs.append([p, 1])
        else:
            runs[-1][1] += 1

    q = len(runs)

    free_cap = 0
    middle = []

    for idx, (st, cnt) in enumerate(runs):
        touch_start = (st == 0)
        touch_end = (st + cnt * L == N)

        if idx == 0 and touch_start:
            free_cap += cnt
        elif idx == q - 1 and touch_end:
            free_cap += cnt
        else:
            middle.append(cnt)

    middle.sort(reverse=True)

    pref = [0]
    s = 0
    for x in middle:
        s += x
        pref.append(s)

    ans = min(M, free_cap)

    # If we use a middle runs, we need:
    # - a cuts to "activate" those runs
    # - at least one selected occurrence in each activated middle run
    # so M - a >= a is necessary.
    max_a = min(len(middle), M // 2)
    for a in range(1, max_a + 1):
        cap = free_cap + pref[a]
        cur = min(M - a, cap)
        if cur > ans:
            ans = cur

    # Special bonus:
    # If the whole string is exactly one run of consecutive ATCODER's,
    # selecting all of them costs count - 1 cuts.
    st0, cnt0 = runs[0]
    if q == 1 and st0 == 0 and st0 + cnt0 * L == N and M >= cnt0 - 1:
        if cnt0 > ans:
            ans = cnt0

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。