概要

リボンから ATCODER という文字列（当たり断片）を、最大 \(M\) 回の切断によってできるだけ多く切り出す問題です。

考察

1. ATCODER の性質とグループ化

ATCODER は長さが 7 です。この文字列は自己重複する周期を持たないため、文字列 \(S\) の中で ATCODER 同士が重なり合って現れることはありません（例えば、ATCODER の途中に別の ATCODER の始まりが重なることはありません）。 したがって、ATCODER が現れる開始位置をすべて列挙し、それらが隣接している（開始位置の差がちょうど 7 である）ものを 1 つの「連続するグループ」としてまとめることができます。

例えば、ATCODERATCODER は長さ 2 のグループ、ATCODERxATCODER は長さ 1 のグループが 2 つ、と分類できます。

2. グループから ATCODER を切り出すための切断回数

グループの長さ（含まれる ATCODER の個数）を \(L\) とします。このグループから ATCODER を切り出すために必要な切断回数を考えます。リボンのどの位置にあるかによって、必要な切断回数が異なります。

パターン1：リボンの端に接していないグループ（内部グループ：Type A）

このグループから \(L\) 個すべてを切り出すには、グループの「左外側」と「右外側」を切る必要があり、さらにグループの内部を \(L-1\) 回切る必要があります。 - 必要な切断回数: \(2 + (L - 1) = L + 1\) 回 - 得られる個数: \(L\) 個 - もし、このグループに \(k\) 回（\(k < L+1\)）の切断しか行わない場合、得られる個数は \(\max(0, k-1)\) 個になります（端を切るために 1 回分損をするため、1 つも切り出せないか、効率が落ちます）。

パターン2：リボンの端に接しているグループ（境界グループ：Type B）

リボンの左端または右端に接しているグループの場合、端側の切断が不要になります。 - 必要な切断回数: \(L\) 回 - 得られる個数: \(L\) 個 - 1 回切るごとに 1 個の ATCODER を確実に得ることができます（効率が常に 1:1 で最もお得です）。

パターン3：リボン全体が 1 つのグループである場合（特殊ケース：Type C）

リボン全体が ATCODER の繰り返しのみで構成されている場合、外側の切断が一切不要です。 - \(L\) 個すべてを得るために必要な切断回数: \(L - 1\) 回 - \(M < L-1\) の場合、 \(M\) 回の切断で \(M\) 個を得ることができます。

3. 貪欲法による最適な割り当て

切断回数 \(M\) をどのように配分すれば、得られる個数を最大化できるかを考えます。

1. 特殊ケース（Type C）の処理: リボン全体が 1 つのグループなら、単純に \(\min(L, M + 1)\)（ただし \(M=0\) なら 0）の要領で計算して終了します。
2. 境界グループ（Type B）への優先配分: 境界グループは 1 回の切断で 1 個の ATCODER を得られるため、最も効率が良いです。まず、境界グループに優先的に切断回数を割り当てます。境界グループの長さの合計を \(B_{sum}\) としたとき：
   • \(M \le B_{sum}\) ならば、答えは \(M\) となります。
   • \(M > B_{sum}\) ならば、境界グループから \(B_{sum}\) 個すべてを回収し、残りの切断回数 \(cur\_M = M - B_{sum}\) を内部グループに配分します。
3. 内部グループ（Type A）への配分（貪欲法）: 内部グループ（長さ \(L\)）を完全に回収するには \(L+1\) 回の切断で \(L\) 個が得られます。このときの回収効率は \(\frac{L}{L+1}\) です。 この値は \(L\) が大きいほど \(1\) に近づくため、長さ \(L\) が大きいグループから優先的に完全に回収するのが最適です。
   • 長さの降順（大きい順）に内部グループをソートします。
   • 残りの切断回数 \(cur\_M\) が \(L+1\) 以上あれば、そのグループを完全回収し、答えに \(L\) を加え、\(cur\_M\) を \(L+1\) 減らします。
   • \(cur\_M\) が \(L+1\) 未満になった場合、そのグループからは最大で \(\max(0, cur\_M - 1)\) 個しか回収できません。これ以上他のグループに配分しても効率は上がらないため、残りをすべてこのグループに使い、探索を終了します。

---

アルゴリズム

1. ATCODER の検出: 文字列 \(S\) を走査し、ATCODER の開始インデックスをすべてリスト P に格納します。
2. グループ化: P を走査し、隣接する（差が 7 の）開始位置を 1 つのグループ（開始位置、終了位置、長さ \(L\)）にまとめます。
3. 特殊ケースの判定: グループが 1 つだけで、それがリボン全体を占める場合は、個別の処理を行って終了します。
4. グループの分類:
   • 左端（開始位置が 0）または右端（終了位置が \(N\)）に接するグループを境界グループ（Type B）とします。
   • それ以外のグループを内部グループ（Type A）とし、その長さを配列 A_sizes に格納します。
5. 貪欲法による計算:
   • 境界グループの長さの合計 \(B_{sum}\) に対して、 \(M \le B_{sum}\) ならば \(M\) を出力します。
   • そうでなければ、境界グループをすべて回収し、残りの \(cur\_M\) を A_sizes を降順ソートしたものに対して貪欲に割り当てます。

---

計算量

• 時間計算量: \(O(N \log N)\)
  • ATCODER の検出とグループ化に \(O(N)\) 時間かかります。
  • 内部グループの数は最大でも \(N / 7\) 個です。これらをソートするのに最大で \(O(N \log N)\) の時間がかかります。
  • 全体として \(O(N \log N)\) となり、 \(N \le 10^6\) でも制限時間内に十分高速に動作します。
• 空間計算量: \(O(N)\)
  • グループ情報を格納する配列や A_sizes のサイズは最大で \(O(N)\) です。

---

実装のポイント

• ATCODER の重なりがない性質: ATCODER 同士は重なり合わないため、単純に左から貪欲に位置を検出するだけで、すべての出現位置を正しくリストアップできます。

• 端の処理: リボンの「左端」と「右端」は切断が不要なため、インデックス 0 と N を用いて、グループが端に接しているかを正確に判定することが重要です。

  ソースコード

#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;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。