概要

この問題は、長さ \(N\) の文字列 \(S\) を「左回転」「右回転」「パターン複製」の3種類の操作を繰り返して目標の文字列 \(T\) に変換するための最小操作回数を求める問題です。

最小操作回数を求める問題であり、状態遷移が明確であるため、幅優先探索（BFS）を用いて解くことができます。

考察

状態空間の広さ

一見すると、長さ \(N=25\) の文字列の状態数は \(2^{25} \approx 3.3 \times 10^7\) 通りあり、愚直な BFS ではメモリや実行時間が厳しそうに見えます。しかし、実際に到達可能な状態数を考えてみると、非常に少ないことがわかります。

1. 回転操作: 文字列 \(S\) を回転させて得られる状態は高々 \(N\) 通りです。
2. パターン複製操作: \(N\) の約数 \(d < N\) を選び、先頭 \(d\) 文字を繰り返します。この操作によって生成される文字列は、必ず周期 \(d\) を持ちます。
   • 周期 \(d\) の文字列の種類数は \(2^d\) 通りです。
   • \(N=24\) の場合（約数が多いため最悪ケースに近い）、約数 \(d\) は \(1, 2, 3, 4, 6, 8, 12\) です。
   • 到達可能な周期的な状態の総数は \(\sum_{d|N, d<N} 2^d\) で表されます。
   • \(N=24\) のとき、 \(2^1 + 2^2 + 2^3 + 2^4 + 2^6 + 2^8 + 2^{12} = 2 + 4 + 8 + 16 + 64 + 256 + 4096 = 4446\) 通りです。

初期状態 \(S\) の回転を含めても、探索すべき状態数はせいぜい数千程度に収まります。これならば BFS で十分に高速に解くことが可能です。

操作のシミュレーション

文字列をそのまま扱うよりも、’A’ を 0、’B’ を 1 とした ビットマスク（整数値） として扱うことで、操作を高速に行えます。

• 左回転: (u >> 1) | ((u & 1) << (N - 1))
• 右回転: ((u << 1) & mask_limit) | (u >> (N - 1))
• パターン複製: 下位 \(d\) ビットを取り出し、それを \(N/d\) 回繰り返した値を作る。

アルゴリズム

1. 初期文字列 \(S\) と目標文字列 \(T\) をビットマスクに変換します。
2. \(N\) の \(N\) 未満の正の約数をすべて列挙します。
3. キューと距離を管理する連想配列（unordered_map）を用意し、初期状態 \(S\) を追加します。
4. キューが空になるまで以下の処理を繰り返します。
   • 現在の状態 \(u\) を取り出す。
   • \(u\) が \(T\) と一致していれば、その時の距離を返して終了。
   • 「左回転」「右回転」を行った状態が未訪問ならキューに追加。
   • 各約数 \(d\) について「パターン複製」を行った状態が未訪問ならキューに追加。
5. キューが空になっても \(T\) に到達できなければ -1 を出力します。

計算量

\(V\) を到達可能な状態数（\(\approx \sum_{d|N, d<N} 2^d + N\)）、\(D\) を \(N\) の約数の個数とします。

• 時間計算量: \(O(V \times D)\)
  • 状態数 \(V\) は最大でも 5000 程度、約数の数 \(D\) は \(N \le 25\) において最大 8 個（\(N=24\) のとき）であるため、非常に高速に動作します。
• 空間計算量: \(O(V)\)
  • 訪問済み状態を記録するハッシュマップのサイズに依存します。

実装のポイント

• ビット操作: 文字列の 0 文字目をビット 0、1 文字目をビット 1… と対応させることで、回転操作をビットシフトと論理和で簡潔に記述できます。

• パターン複製の作り方: pattern = u & ((1 << d) - 1) で先頭 \(d\) 文字分を抽出し、ループで \(N/d\) 回シフトしながら結合します。

• 入出力の高速化: C++ の場合、ios_base::sync_with_stdio(false); cin.tie(NULL); を入れることで実行時間を短縮できます。

  ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

/**
 * Problem Summary:
 * We have a bead sequence represented by a string S of length N (N <= 25).
 * Three operations:
 * 1. Rotate Left: Cyclic shift left (S[0] moves to the end).
 * 2. Rotate Right: Cyclic shift right (S[N-1] moves to the front).
 * 3. Pattern Copy: Choose a divisor d of N (d < N), take the first d characters,
 *    and repeat them N/d times to form a new string.
 * Find the minimum operations to transform S into T.
 * 
 * Approach:
 * The total number of states is small. Any string obtained after a pattern copy
 * is periodic with some period d < N. The number of such strings is at most
 * sum_{d|N, d<N} 2^d. For N=24, this is 4446. Any rotation of a periodic string
 * remains periodic. The only non-periodic strings reachable are cyclic shifts of S.
 * Total states <= N + sum_{d|N, d<N} 2^d, which is around 4500 for N=24.
 * We can use BFS to find the shortest path in this state space.
 */

int main() {
    // Optimize I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;
    string S_str, T_str;
    if (!(cin >> S_str >> T_str)) return 0;

    // Convert strings to bitmasks (A=0, B=1)
    // S[0] is bit 0, S[1] is bit 1, ..., S[N-1] is bit N-1.
    int s_mask = 0;
    for (int i = 0; i < N; ++i) {
        if (S_str[i] == 'B') s_mask |= (1 << i);
    }

    int t_mask = 0;
    for (int i = 0; i < N; ++i) {
        if (T_str[i] == 'B') t_mask |= (1 << i);
    }

    // Pre-calculate divisors of N (d < N)
    vector<int> divs;
    for (int d = 1; d < N; ++d) {
        if (N % d == 0) divs.push_back(d);
    }

    // BFS setup
    queue<int> q;
    unordered_map<int, int> dist;

    q.push(s_mask);
    dist[s_mask] = 0;

    int mask_limit = (1 << N) - 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        int d_u = dist[u];

        // Check if we reached the target
        if (u == t_mask) {
            cout << d_u << endl;
            return 0;
        }

        // 1. Rotate Left: S[0]S[1]...S[N-1] -> S[1]...S[N-1]S[0]
        // Bit 0 moves to bit N-1, bit i moves to bit i-1.
        int v_left = (u >> 1) | ((u & 1) << (N - 1));
        if (dist.find(v_left) == dist.end()) {
            dist[v_left] = d_u + 1;
            q.push(v_left);
        }

        // 2. Rotate Right: S[0]S[1]...S[N-1] -> S[N-1]S[0]...S[N-2]
        // Bit N-1 moves to bit 0, bit i moves to bit i+1.
        int v_right = ((u << 1) & mask_limit) | (u >> (N - 1));
        if (dist.find(v_right) == dist.end()) {
            dist[v_right] = d_u + 1;
            q.push(v_right);
        }

        // 3. Pattern Copy
        for (int d : divs) {
            int pattern = u & ((1 << d) - 1); // First d bits
            int v_copy = 0;
            for (int i = 0; i < N / d; ++i) {
                v_copy |= (pattern << (i * d));
            }
            if (dist.find(v_copy) == dist.end()) {
                dist[v_copy] = d_u + 1;
                q.push(v_copy);
            }
        }
    }

    // Target T not reachable
    cout << -1 << endl;

    return 0;
}

---

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