Overview

This problem asks us to find the maximum number of password fragments ATCODER (hereafter called winning fragments) that can be cut out from a given string \(S\) using at most \(M\) cuts.

We group consecutive adjacent ATCODER occurrences together, and observe that the cost (number of cuts) differs between “groups at the edges” and “groups in the interior” of the string. We solve this by combining a greedy approach with exhaustive search.

---

Analysis

1. Grouping and Cut Cost Observation

The ATCODER occurrences in string \(S\) may appear consecutively adjacent to each other. For example, when two appear consecutively as in ATCODERATCODER, making just one cut in the middle simultaneously separates the right end of the left ATCODER and the left end of the right ATCODER.

In this way, we group consecutive ATCODER occurrences into a single “group” and consider the number of cuts (cost) needed to extract \(k\) winning fragments from that group. The required cost varies depending on where the group is located.

Pattern A: Interior Group (neither end touches the boundary of the string)

For example, consider an interior group of size \(L = 3\): ...[ATCODER][ATCODER][ATCODER]... * Extracting 1: ...|[ATCODER]|... \(\rightarrow\) 2 cuts needed * Extracting 2: ...|[ATCODER]|[ATCODER]|... \(\rightarrow\) 3 cuts needed * Extracting 3: ...|[ATCODER]|[ATCODER]|[ATCODER]|... \(\rightarrow\) 4 cuts needed

In general, the minimum cost to extract \(k\) pieces (\(1 \le k \le L\)) from an interior group is \(k + 1\) cuts. This can be interpreted as “the first piece costs 2, and each additional piece costs 1 more.”

Pattern B: Edge Group (touching the left or right end)

For example, consider a group of size \(L = 3\) at the left end: [ATCODER][ATCODER][ATCODER].... Since the edge is already a boundary, no cut is needed there. * Extracting 1: [ATCODER]|... \(\rightarrow\) 1 cut needed * Extracting 2: [ATCODER]|[ATCODER]|... \(\rightarrow\) 2 cuts needed * Extracting 3: [ATCODER]|[ATCODER]|[ATCODER]|... \(\rightarrow\) 3 cuts needed

In general, the minimum cost to extract \(k\) pieces (\(1 \le k \le L\)) from an edge group is \(k\) cuts. This means “each piece always costs 1 to extract,” making this a very efficient (advantageous) group.

Pattern C: Whole Group (the entire string consists only of consecutive ATCODER)

This is a special case where there is only one group, and it touches both the left and right ends. In this case, since neither end needs to be cut, the minimum cost to extract \(k\) pieces (\(1 \le k \le L\)) is \(k - 1\) cuts. This case is easiest to handle separately as an exception at the beginning.

---

2. Optimal Extraction Strategy

There can be at most 2 edge groups (left end and right end). If we fix the total number of winning fragments recovered from edge groups as \(V\), the number of cuts required is exactly \(V\).

Let the total size of all edge groups be \(B_{\text{sum}}\). Then \(V\) ranges over \(0 \le V \le B_{\text{sum}}\). We consider exhaustively searching over this \(V\).

When \(V\) cuts are allocated to edge groups, the remaining budget (number of cuts) is \(W = M - V\). We use this budget \(W\) to maximize the number of winning fragments obtained from interior groups.

Optimal Recovery from Interior Groups

Let the sizes of interior groups sorted in descending order be \(A_1, A_2, \dots, A_d\). When recovering winning fragments from interior groups, the “first piece” from each group costs 2, so it is optimal to focus on as few groups as possible and recover as much as possible from each selected group (at an additional cost of 1 per piece).

Specifically, suppose we select \(p\) groups starting from the largest. The maximum number recoverable from these \(p\) groups given budget \(W\) is as follows: 1. When all selected groups can be fully recovered (\(\sum_{i=1}^p A_i + p \le W\)): The number recovered equals the total size of the selected groups \(\sum_{i=1}^p A_i\). 2. When the budget is insufficient and recovery is cut short (\(\sum_{i=1}^p A_i + p > W\)): The basic cost of using \(p\) groups (the cost of recovering at least 1 from each group) requires at least \(2p\). The remaining budget \(W - 2p\) is used for additional recovery at cost 1 per piece, so the total recovered is \(p + (W - 2p) = W - p\) pieces.

Therefore, if we find the maximum \(p\) satisfying \(\sum_{i=1}^p A_i + p \le W\) under budget \(W\), we can reliably recover \(S_a[p] = \sum_{i=1}^p A_i\) pieces for that \(p\). Furthermore, if there are still unselected groups remaining, we can partially use one more group to increase the total recovery to \(W - p - 1\) pieces.

As \(V\) increases from \(0\), the budget available for interior groups \(W = M - V\) decreases. Accordingly, the optimal \(p\) also monotonically decreases, so by using the two-pointer technique, we can find the optimal value for all \(V\) in \(O(d)\) total.

---

Algorithm

1. Search for ATCODER: Search for ATCODER in string \(S\) and extract all starting indices without overlaps.
2. Grouping: Group together indices where the difference between adjacent ones is exactly \(7\). For each group, determine whether it “touches an edge” (starting position is \(0\) or ending position is \(N\)).
3. Special Case Handling: If there is only one group and it covers the entire string, handle it as an exception by computing \(\min(L, M+1)\) (or \(M\) when \(M < L-1\)) and terminating.
4. Group Classification and Sorting: Separate edge group sizes into B_sizes and interior group sizes into A_sizes. Sort A_sizes in descending order and prepare prefix sums S_a.
5. Exhaustive Search with Two Pointers: Loop over the number \(V\) of pieces recovered from edge groups from \(0\) to \(B_{\text{sum}}\). For each \(V\), compute the interior budget \(W = M - V\), maintain the maximum \(p\) satisfying \(\sum_{i=1}^p A_i + p \le W\) using two pointers, and update the candidate for the maximum number obtainable.

---

Complexity

• Time Complexity: \(O(N + d \log d)\)

  • Searching for ATCODER and grouping takes \(O(N)\).
  • Sorting interior groups takes \(O(d \log d)\) (\(d\) is the number of groups, at most \(N/7\)).
  • The exhaustive search with two pointers has at most \(B_{\text{sum}} + 1\) loop iterations, and the pointer \(p\) moves at most \(d\) times, resulting in \(O(B_{\text{sum}} + d)\), which is very fast.
  • Overall, this comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used to store indices and group information.

---

Implementation Notes

• Non-overlapping Search: By searching from \(7\) characters ahead of the found index, as in S.find("ATCODER", idx + 7), we correctly extract non-overlapping winning fragments.

• Edge Group Detection: The conditions g[0] == 0 (left end) and g[-1] + 7 == N (right end) accurately determine whether a group touches the string boundary.

• Use of Prefix Sums: To quickly compute the number recoverable from interior groups, we pre-build the prefix sum S_a of A_sizes sorted in descending order, allowing the sum for any \(p\) to be obtained in \(O(1)\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    S = input_data[2]
    
    indices = []
    idx = S.find("ATCODER")
    while idx != -1:
        indices.append(idx)
        idx = S.find("ATCODER", idx + 7)
        
    C = len(indices)
    if C == 0:
        print(0)
        return
        
    groups = []
    current_group = [indices[0]]
    for i in range(1, C):
        if indices[i] == indices[i-1] + 7:
            current_group.append(indices[i])
        else:
            groups.append(current_group)
            current_group = [indices[i]]
    groups.append(current_group)
    
    if len(groups) == 1:
        g = groups[0]
        if g[0] == 0 and g[-1] + 7 == N:
            L = len(g)
            if M >= L - 1:
                print(L)
            else:
                print(M)
            return

    A_sizes = []
    B_sizes = []
    for g in groups:
        is_left = (g[0] == 0)
        is_right = (g[-1] + 7 == N)
        L = len(g)
        if is_left or is_right:
            B_sizes.append(L)
        else:
            A_sizes.append(L)
            
    A_sizes.sort(reverse=True)
    d = len(A_sizes)
    S_a = [0] * (d + 1)
    for i in range(d):
        S_a[i+1] = S_a[i] + A_sizes[i]
        
    B_sum = sum(B_sizes)
    
    ans = 0
    p = d
    for V in range(B_sum + 1):
        W = M - V
        if W < 0:
            break
        while p > 0 and S_a[p] + p > W:
            p -= 1
        val = S_a[p]
        if p < d:
            val = max(val, W - p - 1)
        ans = max(ans, V + val)
        
    ans = min(ans, C)
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.