概要

文字列 \(S\) から、切断によってちょうど ATCODER という文字列になる断片（当たり断片）を最大何個作れるかを求める問題です。切断回数 \(M\) という制限の中で、効率よく当たり断片を切り出す戦略が求められます。

考察

1. 当たり断片の性質

ATCODER という文字列は、自分自身と重ねて現れることがありません（例：ATCODERATCODER の中に、ずれた形で ATCODER が隠れていることはありません）。したがって、文字列 \(S\) の中から ATCODER と一致する箇所を単純にすべて列挙し、それらが連続しているかどうかを確認すればよいことになります。

2. 切断コストの分析

「当たり断片」を 1 つ作るために必要な切断回数は、その断片が文字列のどこにあるかによって変わります。

• ケースA：リボンの端にある場合
  • 例：ATCODER... や ...ATCODER
  • 端にある 1 つの ATCODER を切り出すには、1 回の切断で済みます。
  • さらにその隣も ATCODER であれば、もう 1 回の切断で追加の当たり断片が得られます。
• ケースB：リボンの途中にある場合
  • 例：...XATCODER Y... （X, Y は ATCODER の一部ではない文字）
  • 最初の 1 つを切り出すには、左右を切り離すために 2 回の切断が必要です。
  • ただし、連続して ATCODER が並んでいる場合（例：...XATCODERATCODERY...）、2 つ目以降は 1 回の追加切断で済みます。
• ケースC：リボン全体が ATCODER の繰り返しである場合
  • \(k\) 個の ATCODER が並んでいるとき、\(k-1\) 回の切断で \(k\) 個すべての当たり断片が得られます。

3. 貪欲法による戦略

限られた切断回数 \(M\) で個数を最大化するためには、「少ないコストで増やせるもの」から優先的に処理します。

1. 端にあるブロック: 最初の 1 つがコスト 1、以降もコスト 1。非常に効率が良いです。
2. 途中にあるブロック: 最初の 1 つがコスト 2、以降はコスト 1。
   • 途中のブロックが複数ある場合、「連続している数が多いブロック」から優先的に処理すべきです。なぜなら、どのブロックも「最初の 1 つ」にコスト 2 という「入場料」がかかるため、一度入場料を払ったらそのブロックからできるだけ多くの断片を回収する方が、トータルの「入場料」の回数を減らせるからです。

アルゴリズム

1. 文字列 \(S\) から ATCODER が現れる位置をすべて探し出します。
2. 連続して隣り合っている ATCODER をグループ（ブロック）化します。
3. 各ブロックを「端に接しているか」「途中に浮いているか」「リボン全体か」で分類します。
4. 以下の優先順位で \(M\) を消費して当たり断片をカウントします：
   • リボン全体が当たり断片の連続である特殊ケースを処理。
   • 端に接しているブロックを処理（1 カットにつき 1 個）。
   • 途中のブロックを、サイズ（連続数）が大きい順に処理。
     • 最初の 1 個に 2 カット、その後は 1 カットにつき 1 個。

計算量

• 時間計算量: \(O(N)\)
  • 文字列の検索、ブロック化、ソート（ブロック数は最大 \(N/7\)）を含め、文字列長 \(N\) に対して線形時間で動作します。
• 空間計算量: \(O(N)\)
  • 文字列 \(S\) および出現位置を記録するリストの保存に \(O(N)\) のメモリを使用します。

実装のポイント

• ブロックの分類: 文字列の先頭（インデックス 0）から始まっているか、末尾（インデックス \(N\)）で終わっているかを判定することで、端のブロックかどうかが分かります。

• 途中ブロックのソート: middle_blocks_sizes.sort(reverse=True) とすることで、長い連続から優先的にカットし、コスト 2 がかかる「最初の 1 個」の発生回数を最小限に抑えます。

• 切断回数の管理: 残りの \(M\) が 1 回しかない場合、途中のブロックからは 1 つも当たり断片を切り出せない（2 回必要なので）ことに注意が必要です。

  ソースコード

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

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