Overview

This problem asks for the maximum number of fragments that exactly match the string ATCODER (winning fragments) that can be produced by cutting string \(S\). The challenge is to find an efficient strategy for cutting out winning fragments within the constraint of at most \(M\) cuts.

Analysis

1. Properties of Winning Fragments

The string ATCODER never overlaps with itself (for example, in ATCODERATCODER, there is no hidden ATCODER appearing in a shifted position). Therefore, we can simply enumerate all positions in string \(S\) that match ATCODER and check whether they are consecutive.

2. Analysis of Cutting Costs

The number of cuts required to produce one “winning fragment” depends on where that fragment is located in the string.

• Case A: Located at the edge of the ribbon
  • Example: ATCODER... or ...ATCODER
  • Cutting out a single ATCODER at the edge requires only 1 cut.
  • If the adjacent portion is also ATCODER, each additional winning fragment requires only 1 more cut.
• Case B: Located in the middle of the ribbon
  • Example: ...XATCODER Y... (where X, Y are characters not part of ATCODER)
  • Cutting out the first one requires 2 cuts to separate it from both sides.
  • However, if multiple ATCODER strings are consecutive (e.g., ...XATCODERATCODERY...), each subsequent one requires only 1 additional cut.
• Case C: The entire ribbon consists of repeated ATCODER
  • When \(k\) copies of ATCODER are lined up forming the entire string, \(k-1\) cuts yield all \(k\) winning fragments.

3. Greedy Strategy

To maximize the count within the limited number of cuts \(M\), we prioritize processing items that can be gained at lower cost.

1. Blocks at the edges: The first one costs 1, and each subsequent one also costs 1. This is very efficient.
2. Blocks in the middle: The first one costs 2, and each subsequent one costs 1.
   • When there are multiple middle blocks, we should prioritize blocks with more consecutive occurrences. This is because every block incurs a cost of 2 as an “entry fee” for the first fragment, so once we pay the entry fee, we should recover as many fragments as possible from that block to minimize the total number of “entry fees” paid.

Algorithm

1. Find all positions in string \(S\) where ATCODER appears.
2. Group consecutive adjacent ATCODER occurrences into blocks.
3. Classify each block as “touching an edge,” “floating in the middle,” or “spanning the entire ribbon.”
4. Consume \(M\) cuts in the following priority order to count winning fragments:
   • Handle the special case where the entire ribbon consists of consecutive winning fragments.
   • Process blocks touching an edge (1 fragment per 1 cut).
   • Process middle blocks in decreasing order of size (number of consecutive occurrences).
     • The first fragment costs 2 cuts, then each subsequent one costs 1 cut.

Complexity

• Time Complexity: \(O(N)\)
  • Including string searching, block formation, and sorting (the number of blocks is at most \(N/7\)), the algorithm runs in linear time with respect to string length \(N\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store string \(S\) and the list of occurrence positions.

Implementation Notes

• Block classification: By checking whether a block starts at the beginning of the string (index 0) or ends at the end of the string (index \(N\)), we can determine whether it is an edge block.

• Sorting middle blocks: Using middle_blocks_sizes.sort(reverse=True) ensures that longer consecutive sequences are cut first, minimizing the number of times the cost-2 “first fragment” is incurred.

• Managing remaining cuts: Note that if the remaining \(M\) is only 1, no winning fragments can be cut from middle blocks (since 2 cuts are required).

  Source Code

import sys

def solve():
    # Read all input data at once for speed
    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]
    
    target = "ATCODER"
    len_t = len(target)
    
    # Find all start indices of non-overlapping "ATCODER" occurrences.
    # Since "ATCODER" has no prefix that is also a suffix,
    # the occurrences found will naturally be non-overlapping.
    indices = []
    pos = s.find(target)
    while pos != -1:
        indices.append(pos)
        pos = s.find(target, pos + len_t)
        
    if not indices:
        print(0)
        return

    # Group occurrences into maximal blocks of touching occurrences.
    # Two occurrences touch if the end of one is the start of the next.
    blocks = []
    current_block = [indices[0]]
    for i in range(1, len(indices)):
        if indices[i] == indices[i-1] + len_t:
            current_block.append(indices[i])
        else:
            blocks.append(current_block)
            current_block = [indices[i]]
    blocks.append(current_block)
    
    # Classify blocks based on whether they touch the ribbon's ends.
    # A block's cost depends on its position relative to the ribbon boundaries.
    full_block_size = None
    end_blocks_sizes = []
    middle_blocks_sizes = []
    
    for b in blocks:
        start_pos = b[0]
        end_pos = b[-1] + len_t
        size = len(b)
        
        if start_pos == 0 and end_pos == n:
            # Case where the entire ribbon is a sequence of "ATCODER"s.
            full_block_size = size
        elif start_pos == 0 or end_pos == n:
            # Case where the sequence touches only one end of the ribbon.
            end_blocks_sizes.append(size)
        else:
            # Case where the sequence is surrounded by non-target characters.
            middle_blocks_sizes.append(size)
            
    # If the entire ribbon consists only of "ATCODER" fragments.
    if full_block_size is not None:
        # With k fragments, we need k-1 cuts to separate them all.
        # If cuts allowed m < k-1, we can get m winning fragments.
        if m >= full_block_size - 1:
            print(full_block_size)
        else:
            print(m)
        return
        
    ans = 0
    # Greedy strategy: prioritize blocks with the lowest initial cost.
    # End blocks: The 1st fragment costs 1 cut, each subsequent costs 1 cut.
    for size in end_blocks_sizes:
        p = min(m, size)
        ans += p
        m -= p
        
    # Middle blocks: The 1st fragment costs 2 cuts, each subsequent costs 1 cut.
    # To maximize fragments, we pick from the largest middle blocks first.
    middle_blocks_sizes.sort(reverse=True)
    for size in middle_blocks_sizes:
        if m >= 2:
            # We need at least 2 cuts to isolate the first fragment in a middle block.
            # With 'm' cuts available, we can extract up to 'm-1' fragments from one block.
            p = min(m - 1, size)
            ans += p
            m -= (p + 1)
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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