Official

C - リボンを切って合言葉を集めよう / Cut the Ribbon and Collect the Passwords Editorial by admin Editorial for printing

gemini-3.5-flash-thinking

概要

この問題は、与えられた文字列 \(S\) から、切断回数 \(M\) 回以内で合言葉 ATCODER（以下、当たり断片と呼びます）を最大で何個切り出せるかを求める問題です。

連続して隣り合う ATCODER をグループとしてまとめ、文字列の「端にあるグループ」と「内部にあるグループ」で切り出すためのコスト（切断回数）が異なることに注目して、貪欲法と全探索を組み合わせて解きます。

考察

1. グループ分けと切断コストの観察

文字列 \(S\) の中にある ATCODER は、隣り合って連続している場合があります。 例えば、ATCODERATCODER のように2つ連続している場合、その真ん中を1回切るだけで、左の ATCODER の右端と、右の ATCODER の左端を同時に切り出すことができます。

このように、連続する ATCODER を1つの「グループ」としてまとめ、そのグループから \(k\) 個の当たり断片を切り出すために必要な切断回数（コスト）を考えます。グループが置かれている場所によって、必要なコストが変わります。

パターンA：内部グループ（両端が文字列の端に接していない）

例えば、サイズ \(L = 3\) の内部グループ ...[ATCODER][ATCODER][ATCODER]... を考えます。 * 1個切り出す場合：...|[ATCODER]|... \(\rightarrow\) 2回の切断が必要 * 2個切り出す場合：...|[ATCODER]|[ATCODER]|... \(\rightarrow\) 3回の切断が必要 * 3個切り出す場合：...|[ATCODER]|[ATCODER]|[ATCODER]|... \(\rightarrow\) 4回の切断が必要

一般に、内部グループから \(k\) 個（\(1 \le k \le L\)）を切り出すための最小コストは \(k + 1\) 回 です。 これは、「最初の1個目を切り出すのにコスト 2 がかかり、2個目以降は1個追加するごとに追加コスト 1 がかかる」と解釈できます。

パターンB：端グループ（左端または右端に接している）

例えば、左端にあるサイズ \(L = 3\) のグループ [ATCODER][ATCODER][ATCODER]... を考えます。端の部分はすでに切れているため、切断する必要がありません。 * 1個切り出す場合：[ATCODER]|... \(\rightarrow\) 1回の切断が必要 * 2個切り出す場合：[ATCODER]|[ATCODER]|... \(\rightarrow\) 2回の切断が必要 * 3個切り出す場合：[ATCODER]|[ATCODER]|[ATCODER]|... \(\rightarrow\) 3回の切断が必要

一般に、端グループから \(k\) 個（\(1 \le k \le L\)）を切り出すための最小コストは \(k\) 回 です。 これは、「常に1個あたりコスト 1 で切り出せる」ため、非常に効率が良い（オトクな）グループです。

パターンC：全体グループ（文字列全体が ATCODER の連続のみで構成されている）

グループが1つだけで、それが左端かつ右端でもある特殊なケースです。 この場合、両端とも切る必要がないため、\(k\) 個（\(1 \le k \le L\)）切り出すための最小コストは \(k - 1\) 回 になります。 このケースは、例外として最初に個別に処理するのが簡単です。

2. 最適な切り出し方の戦略

端グループは最大で2つ（左端と右端）しか存在しません。 端グループから回収する当たり断片の総数を \(V\) 個と決め打つと、それに必要な切断回数もちょうど \(V\) 回になります。

端グループ全体のサイズ合計を \(B_{\text{sum}}\) とすると、 \(V\) は \(0 \le V \le B_{\text{sum}}\) の範囲を動きます。 この \(V\) を全探索することを考えます。

端グループに \(V\) 回の切断を割り当てたとき、残りの予算（切断回数）は \(W = M - V\) 回となります。 この予算 \(W\) を使って、内部グループから得られる当たり断片の個数を最大化します。

内部グループからの最適な回収方法

内部グループのサイズを降順にソートしたものを \(A_1, A_2, \dots, A_d\) とします。 内部グループから当たり断片を回収する場合、グループの「最初の1個」にはコスト 2 がかかるため、できるだけ少ない個数のグループに絞って、選んだグループから限界まで（追加コスト1で）回収するのが最適です。

具体的には、サイズが大きい方から \(p\) 個のグループを選ぶとします。 この \(p\) 個のグループから回収できる最大個数は、予算 \(W\) に対して以下のようになります。 1. 選んだグループをすべて満杯まで回収できる場合（\(\sum_{i=1}^p A_i + p \le W\)） 回収できる個数は、選んだグループのサイズの総和 \(\sum_{i=1}^p A_i\) となります。 2. 予算が足りず、途中で打ち切る場合（\(\sum_{i=1}^p A_i + p > W\)） グループを \(p\) 個使うための基本コスト（各グループから1個以上回収するコスト）は、各グループに「最初の1個（コスト2）」を割り当てるため、最低でも \(2p\) 必要です。 残りの予算 \(W - 2p\) を使って、1個あたりコスト1で追加回収するため、回収できる総数は \(p + (W - 2p) = W - p\) 個となります。

したがって、予算 \(W\) のもとで \(\sum_{i=1}^p A_i + p \le W\) を満たす最大の \(p\) を求めれば、その \(p\) に対して確実に \(S_a[p] = \sum_{i=1}^p A_i\) 個を回収できます。 さらに、まだ選んでいないグループがあるなら、もう1つのグループを中途半端に使うことで、合計 \(W - p - 1\) 個まで回収個数を増やすことができます。

\(V\) を \(0\) から増やしていくと、内部グループに使える予算 \(W = M - V\) は減少していきます。これに伴い、最適な \(p\) も単調減少するため、しゃくとり法（Two Pointers）を用いることで、すべての \(V\) に対する最適値を全体で \(O(d)\) で探索できます。

アルゴリズム

  1. ATCODER の検索: 文字列 \(S\) から ATCODER を検索し、重なり合わないように開始インデックスをすべて抽出します。
  2. グループ分け: 隣り合うインデックスの差がちょうど \(7\) であるものを同じグループにまとめます。 各グループについて、「端に接しているか（開始位置が \(0\) または終了位置が \(N\)）」を判定します。
  3. 特殊ケースの処理: グループが1つだけで、それが文字列全体を覆っている場合、例外処理として \(\min(L, M+1)\) （ただし \(M < L-1\) のときは \(M\)）を計算して終了します。
  4. グループの分類とソート: 端に接しているグループのサイズを B_sizes、内部グループのサイズを A_sizes に分けます。 A_sizes を降順にソートし、累積和 S_a を用意します。
  5. 全探索としゃくとり法: 端グループから回収する個数 \(V\) を \(0\) から \(B_{\text{sum}}\) までループします。 各 \(V\) に対し、内部の予算 \(W = M - V\) を計算し、\(\sum_{i=1}^p A_i + p \le W\) を満たす最大の \(p\) をしゃくとり法で維持しながら、得られる最大個数の候補を更新していきます。

計算量

  • 時間計算量: \(O(N + d \log d)\)

    • ATCODER の検索およびグループ分けに \(O(N)\) かかります。
    • 内部グループのソートに \(O(d \log d)\) かかります（\(d\) はグループ数で、最大でも \(N/7\)）。
    • しゃくとり法による全探索は、ループ回数が \(B_{\text{sum}} + 1\) 回、ポインタ \(p\) の移動回数が高々 \(d\) 回であるため、 \(O(B_{\text{sum}} + d)\) となり非常に高速です。
    • 全体として、制限時間内に余裕で間に合います。

  • 空間計算量: \(O(N)\)

    • indices やグループの情報を格納するために \(O(N)\) のメモリを使用します。

実装のポイント

  • 重なり合わない検索: S.find("ATCODER", idx + 7) のように、見つかったインデックスの \(7\) 文字先から次の検索を開始することで、正しく重なりのない当たり断片を抽出しています。

  • 端グループの判定: g[0] == 0（左端）や g[-1] + 7 == N（右端）という条件式で、グループが文字列の境界に接しているかを正確に判定しています。

  • 累積和の活用: 内部グループから回収できる個数を高速に求めるため、降順ソートした A_sizes の累積和 S_a をあらかじめ構築しておくことで、任意の \(p\) に対する総和を \(O(1)\) で取得できるようにしています。

    ソースコード

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

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

posted:
last update: