概要

長さ \(N\) の A / B 文字列を状態とみなし、3 種類の操作で \(S\) から \(T\) へ変化させる最小操作回数を求めます。

各操作のコストはすべて \(1\) なので、状態を頂点、操作を辺とするグラフ上で 幅優先探索（BFS） を行えば最短手数が求められます。

考察

この問題では、現在のビーズ列に対して以下の操作ができます。

• 左回転
• 右回転
• 先頭 \(d\) 文字を繰り返して全体を置き換える操作

例えば、\(N = 6\) で現在の文字列が ABBAAB のとき、

• 左回転すると BBAABA
• 右回転すると BABBAA
• \(d = 2\) を選ぶと、先頭 \(2\) 文字 AB を \(3\) 回繰り返して ABABAB

になります。

ここで重要なのは、状態数が有限であることです。

文字は A と B の \(2\) 種類で、長さは \(N\) なので、あり得る文字列は最大で

\(2^N\)

通りです。

操作列自体は無限に考えられます。例えば、左回転と右回転を繰り返すだけで、同じ状態に何度でも戻ることができます。

そのため、単純に操作列を全部試すような方法では終わりません。

しかし、一度訪れた状態を再び調べないようにすれば、調べる状態数は高々 \(2^N\) 個です。

また、すべての操作のコストは同じく \(1\) なので、最短手数を求めるには BFS が適しています。

BFS では、距離 \(0\) の状態、距離 \(1\) の状態、距離 \(2\) の状態、……という順に探索するため、初めて \(T\) に到達したときの距離が最小操作回数になります。

アルゴリズム

1. \(N\) の正の約数 \(d\) のうち、\(d < N\) をすべて列挙しておく。
2. 始点を \(S\) として BFS を開始する。
3. 各状態 \(x\) について、次の遷移先を作る。
   • 左回転: x[1:] + x[0]
   • 右回転: x[-1] + x[:-1]
   • 各約数 \(d\) について、先頭 \(d\) 文字を繰り返す:
     • x[:d] * (N // d)
4. まだ訪れていない状態なら、距離を現在の距離 \(+1\) としてキューに追加する。
5. BFS 中に \(T\) が見つかれば、その距離を出力する。
6. 探索が終わっても \(T\) に到達できなければ -1 を出力する。

BFS の流れは以下のようになります。

dist[S] = 0
queue = [S]

while queue が空でない:
    x = queue から取り出す

    x == T なら dist[x] を答えとして出力

    x から 1 回の操作で行ける状態をすべて作る
    未訪問なら距離を記録して queue に追加

計算量

\(R\) を \(S\) から到達可能な状態数、\(D\) を \(N\) の \(N\) 未満の正の約数の個数とします。

各状態からの遷移は、左回転・右回転の \(2\) 個と、パターン複製の \(D\) 個です。

また、文字列の生成には長さ \(N\) に比例する時間がかかります。

• 時間計算量: \(O(R(D+2)N)\)
  ただし \(R \leq 2^N\) なので、上界としては \(O(2^N(D+2)N)\)
• 空間計算量: \(O(RN)\)

実装のポイント

dist を辞書として使い、各文字列に対する最短距離を記録します。

dist = {S: 0}

キューには BFS 用に deque を使います。

from collections import deque
q = deque([S])

パターン複製で使う約数は、毎回調べる必要はないため、最初に列挙しておきます。

divs = [(d, N // d) for d in range(1, N) if N % d == 0]

これにより、各状態では列挙済みの約数に対して

y = x[:d] * m

とするだけで遷移先を作れます。

また、回転操作で同じ文字列になる場合や、別の操作で同じ状態に到達する場合がありますが、dist に存在するかを確認することで重複探索を防げます。

ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    T = input().strip()

    divs = [(d, N // d) for d in range(1, N) if N % d == 0]

    dist = {S: 0}
    q = deque([S])

    while q:
        x = q.popleft()
        cur = dist[x]

        if x == T:
            print(cur)
            return

        nd = cur + 1

        y = x[1:] + x[0]
        if y not in dist:
            dist[y] = nd
            q.append(y)

        y = x[-1] + x[:-1]
        if y not in dist:
            dist[y] = nd
            q.append(y)

        for d, m in divs:
            y = x[:d] * m
            if y not in dist:
                dist[y] = nd
                q.append(y)

    print(-1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。