Overview

This problem asks you to cut out as many ATCODER substrings (winning fragments) as possible from a ribbon using at most \(M\) cuts.

Analysis

1. Properties of ATCODER and Grouping

ATCODER has length 7. Since this string has no self-overlapping period, occurrences of ATCODER in string \(S\) cannot overlap with each other (for example, the beginning of another ATCODER cannot overlap with the middle of one ATCODER). Therefore, we can enumerate all starting positions where ATCODER appears, and group together those that are adjacent (i.e., starting positions differ by exactly 7) into a single “consecutive group.”

For example, ATCODERATCODER forms a group of length 2, while ATCODERxATCODER forms two separate groups each of length 1.

2. Number of Cuts Needed to Extract ATCODER from a Group

Let \(L\) be the length of a group (the number of ATCODER instances it contains). We consider the number of cuts needed to extract ATCODER from this group. The required number of cuts varies depending on the group’s position on the ribbon.

Pattern 1: Groups Not Touching the Edge of the Ribbon (Internal Groups: Type A)

To extract all \(L\) instances from this group, we need to cut the “left outside” and “right outside” of the group, and additionally make \(L-1\) internal cuts. - Required number of cuts: \(2 + (L - 1) = L + 1\) - Instances obtained: \(L\) - If only \(k\) cuts (\(k < L+1\)) are allocated to this group, the number of instances obtained is \(\max(0, k-1)\) (one cut is “wasted” on separating the group from the rest, resulting in either no extraction or reduced efficiency).

Pattern 2: Groups Touching the Edge of the Ribbon (Boundary Groups: Type B)

For groups touching the left or right edge of the ribbon, the cut on the edge side is unnecessary. - Required number of cuts: \(L\) - Instances obtained: \(L\) - Each cut reliably yields one ATCODER (the efficiency is always 1:1, making this the most cost-effective).

Pattern 3: The Entire Ribbon is a Single Group (Special Case: Type C)

If the entire ribbon consists solely of repeated ATCODER, no external cuts are needed at all. - Required number of cuts to obtain all \(L\) instances: \(L - 1\) - If \(M < L-1\), then \(M\) cuts yield \(M\) instances.

3. Optimal Allocation via Greedy Method

We consider how to allocate the \(M\) cuts to maximize the number of instances obtained.

1. Handling the Special Case (Type C): If the entire ribbon is a single group, we simply compute \(\min(L, M + 1)\) (with the caveat that if \(M=0\) the answer is 0) and terminate.
2. Priority Allocation to Boundary Groups (Type B): Boundary groups yield one ATCODER per cut, giving the best efficiency. We first allocate cuts preferentially to boundary groups. Let \(B_{sum}\) be the total length of all boundary groups:
   • If \(M \le B_{sum}\), the answer is \(M\).
   • If \(M > B_{sum}\), we fully recover all \(B_{sum}\) instances from boundary groups, and distribute the remaining cuts \(cur\_M = M - B_{sum}\) to internal groups.
3. Allocation to Internal Groups (Type A) (Greedy Method): Fully recovering an internal group of length \(L\) requires \(L+1\) cuts and yields \(L\) instances. The recovery efficiency is \(\frac{L}{L+1}\). Since this value approaches \(1\) as \(L\) increases, it is optimal to fully recover groups with larger length \(L\) first.
   • Sort internal groups in descending order of length.
   • If the remaining cuts \(cur\_M\) is at least \(L+1\), fully recover that group, add \(L\) to the answer, and decrease \(cur\_M\) by \(L+1\).
   • If \(cur\_M\) is less than \(L+1\), we can only recover at most \(\max(0, cur\_M - 1)\) instances from that group. Since distributing to other groups won’t improve efficiency, we use all remaining cuts on this group and terminate the search.

---

Algorithm

1. Detection of ATCODER: Scan string \(S\) and store all starting indices of ATCODER in a list P.
2. Grouping: Scan P and merge adjacent starting positions (those differing by 7) into a single group (start position, end position, length \(L\)).
3. Special Case Check: If there is only one group and it spans the entire ribbon, handle it separately and terminate.
4. Group Classification:
   • Groups touching the left edge (starting position is 0) or the right edge (ending position is \(N\)) are classified as boundary groups (Type B).
   • All other groups are classified as internal groups (Type A), and their lengths are stored in the array A_sizes.
5. Greedy Computation:
   • If \(M \le B_{sum}\) (the total length of boundary groups), output \(M\).
   • Otherwise, fully recover all boundary groups, and greedily allocate the remaining \(cur\_M\) to A_sizes sorted in descending order.

---

Complexity

• Time Complexity: \(O(N \log N)\)
  • Detection of ATCODER and grouping takes \(O(N)\) time.
  • The number of internal groups is at most \(N / 7\). Sorting them takes at most \(O(N \log N)\) time.
  • Overall, this is \(O(N \log N)\), which runs well within the time limit even for \(N \le 10^6\).
• Space Complexity: \(O(N)\)
  • The arrays storing group information and A_sizes have size at most \(O(N)\).

---

Implementation Notes

• Non-overlapping Property of ATCODER: Since ATCODER instances cannot overlap, simply detecting positions greedily from left to right correctly lists all occurrences.

• Edge Handling: Since the “left edge” and “right edge” of the ribbon do not require cuts, it is important to accurately determine whether a group touches the edge using indices 0 and N.

  Source Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Group {
    int start;
    int end;
    int len;
};

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    string S;
    cin >> S;

    // Step 1: Find all starting positions of "ATCODER"
    vector<int> P;
    for (int i = 0; i + 6 < N; ++i) {
        if (S[i] == 'A' && S[i+1] == 'T' && S[i+2] == 'C' && S[i+3] == 'O' && 
            S[i+4] == 'D' && S[i+5] == 'E' && S[i+6] == 'R') {
            P.push_back(i);
        }
    }

    if (P.empty()) {
        cout << 0 << "\n";
        return 0;
    }

    // Step 2: Group consecutive occurrences
    vector<Group> groups;
    int start = P[0];
    int len = 1;
    for (size_t i = 1; i < P.size(); ++i) {
        if (P[i] == P[i-1] + 7) {
            len++;
        } else {
            groups.push_back({start, start + 7 * len, len});
            start = P[i];
            len = 1;
        }
    }
    groups.push_back({start, start + 7 * len, len});

    // Step 3: Handle Type C (The entire ribbon is one contiguous block of "ATCODER")
    if (groups.size() == 1 && groups[0].start == 0 && groups[0].end == N) {
        int L = groups[0].len;
        if (M >= L - 1) {
            cout << L << "\n";
        } else {
            cout << M << "\n";
        }
        return 0;
    }

    // Step 4: Classify other blocks into Type B (boundary) and Type A (internal)
    int L_left = 0;
    int L_right = 0;
    vector<int> A_sizes;
    for (const auto& g : groups) {
        if (g.start == 0) {
            L_left = g.len;
        } else if (g.end == N) {
            L_right = g.len;
        } else {
            A_sizes.push_back(g.len);
        }
    }

    // Step 5: Greedy allocation
    int B_sum = L_left + L_right;
    if (M <= B_sum) {
        cout << M << "\n";
    } else {
        int ans = B_sum;
        int cur_M = M - B_sum;
        // Sort Type A block sizes in descending order to maximize efficiency
        sort(A_sizes.rbegin(), A_sizes.rend());
        for (int L : A_sizes) {
            if (cur_M >= L + 1) {
                cur_M -= (L + 1);
                ans += L;
            } else {
                ans += max(0, cur_M - 1);
                cur_M = 0;
                break;
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

---

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