Overview

Find all occurrence positions of ATCODER, group consecutive adjacent occurrences together, and you can cleanly organize how many cuts are needed to produce a certain number of winning fragments from each group.
The problem then reduces to counting “how many fragments each cut adds” and “the initial cost to use intermediate groups.”

Analysis

First, a winning fragment must exactly match the string ATCODER.
Therefore, the only candidates are the positions where ATCODER appears in \(S\).

1. Occurrences of ATCODER do not overlap

ATCODER has no “proper prefix = proper suffix” match.
Therefore, two occurrences of ATCODER cannot partially overlap.

For example, let the length be \(L=8\). If two occurrences overlap, then for some \(1 \le d < L\):

• The suffix of length \(L-d\) of the first occurrence
• The prefix of length \(L-d\) of the second occurrence

would have to match, but this never happens for ATCODER.

Therefore, occurrence positions are either:

• Separated (with other characters in between)
• Exactly adjacent (starting positions differ by \(8\))

---

2. Why naive approaches are too slow

For example, approaches like:

• Trying all possible cutting positions
• DP tracking “how many characters we’ve seen and how many cuts we’ve made”

would be far too slow since \(N \le 10^6\).
A complexity like \(O(NM)\) is impossible.

So we focus on the structure of ATCODER occurrences and organize things more efficiently.

---

3. Grouping consecutive occurrences into blocks

We treat consecutive ATCODER occurrences with no gaps as a single block.

For example:

• ATCODERATCODERATCODER is a block of size 3
• If other characters appear in between, they form separate blocks

Hereafter, assume one block contains \(c\) consecutive ATCODER occurrences.

---

4. Number of cuts needed to extract \(x\) pieces from one block

This is the essence of the problem.

Blocks touching the left or right edge

For example, if the string starts with ATCODERATCODER..., it’s most efficient to take \(x\) pieces from the beginning.

• To extract \(x\) ATCODER occurrences as \(x\) separate fragments:
• Cut \(x-1\) times at internal boundaries within the block
• Cut 1 more time to separate from the remainder

So the required number of cuts is \(x\) times.

In other words, for edge blocks:
“1 cut per winning fragment”
is the rate of increase.

---

Blocks not touching either end (intermediate blocks)

To extract \(x\) pieces from an intermediate block:

• 1 cut to separate from the left side
• 1 cut to separate from the right side
• \(x-1\) cuts for internal boundaries

So the total is \(x+1\) cuts.

This means intermediate blocks:

• Need an extra 1 cut to start using them
• After that, each additional piece costs 1 cut

This “first extra cut” can be thought of as a startup cost.

---

5. What to choose for optimality

Let free_cap be the total number of ATCODER occurrences in edge blocks.
This is “the number of pieces obtainable at 1 cut each without startup cost.”

Let the sizes of the intermediate blocks be \(c_1, c_2, \dots\).

When deciding to use \(a\) intermediate blocks

To use those \(a\) blocks, we first need \(a\) cuts as startup cost.
The remaining \(M-a\) cuts can each produce 1 winning fragment.

Therefore, the number of winning fragments we can make is the minimum of:

• Upper bound from remaining cuts: \(M-a\)
• Upper bound from existing occurrences: free_cap + total size of the chosen a blocks

That is:

\[ \text{answer}(a)=\min\left(M-a,\ \text{free\_cap}+\sum(\text{sizes of the chosen }a\text{ blocks})\right) \]

For a fixed \(a\), the optimal choice is to pick the \(a\) largest intermediate blocks.
So we sort intermediate block sizes in descending order and compute prefix sums.

---

6. Special case: the entire string is a repetition of ATCODER

For example:

• ATCODERATCODER

When the entire string forms one continuous block, it’s slightly special.

In this case, to split everything into ATCODER pieces, there’s no need to cut the outer boundaries, so:

• If there are \(c\) ATCODER occurrences
• The required number of cuts is \(c-1\) times

This is 1 cut cheaper than the usual “1 cut per piece.”
For example, if there are 2 consecutive occurrences, cutting once in the middle gives both as winning fragments.

Therefore, only this case needs special handling at the end.

Algorithm

1. Let T = "ATCODER" and check all substrings of length \(8\) to enumerate all starting positions where T occurs.
2. Connect positions whose difference is exactly \(8\) to form “consecutive occurrence blocks.”
   Store each block as (starting position, count).
3. For each block:
   • If it’s a leading block touching the left edge, add its count to free_cap
   • If it’s a trailing block touching the right edge, add its count to free_cap
   • Otherwise, add its count to the array middle as an intermediate block
4. Sort middle in descending order and compute prefix sums pref.
5. For using \(a\) intermediate blocks, enumerate \(a=0,1,\dots,\min(|middle|,\lfloor M/2 \rfloor)\):
   • Capacity cap = free_cap + pref[a]
   • Computable count min(M - a, cap) Update the maximum.
6. Additionally, if “the entire string is one continuous block” with \(c\) ATCODER occurrences, and \(M \ge c-1\), the answer is at least \(c\), so reflect this.

Complexity

• Time complexity: \(O(N + K \log K)\)
• Space complexity: \(O(K)\)

Here \(K\) is the number of ATCODER occurrence blocks.
Since the length of ATCODER is fixed at \(8\), the occurrence search is effectively \(O(N)\).

Implementation Notes

• Since the length of ATCODER is fixed, checking S[i:i+8] == "ATCODER" at each position is \(O(N)\) overall.

• Since ATCODER occurrences don’t overlap, you can scan occurrence positions from left to right and form blocks by checking “whether the difference is 8.”

• To use \(a\) intermediate blocks, you need to take at least 1 piece from each block for it to be meaningful, so checking up to \(a \le M/2\) is sufficient.

• Only the case where “the entire string is a repetition of ATCODER” requires special handling because cuts at both ends become unnecessary.

  Source Code

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()

---

This editorial was generated by gpt-5.4-high.