概要

この問題は、文字列（ビーズ列）を頂点、1回の操作を辺とみなした最短路問題です。
各操作のコストはすべて 1 なので、初期状態 \(S\) から幅優先探索（BFS）を行えば、目標 \(T\) までの最小操作回数を求められます。

考察

重要なポイントは次の2つです。

1. 操作回数最小 → 「重みなしグラフの最短距離」なので BFS が適切
   
2. \(N \le 25\) なので、状態（長さ \(N\) の A/B 文字列）をビット列として持つと高速化できる

---

各状態は長さ \(N\) の2値文字列なので、理論上の状態数は最大 \(2^N\) 個です（\(N=25\) なら約 3,300 万）。
全状態を最初から列挙するのではなく、\(S\) から到達可能な状態だけを BFS で探索します。

なぜ素朴実装だと厳しいか

文字列のまま操作を作ると、各遷移で文字列コピーが多発し、探索全体で遅くなりやすいです。
そこでコードでは文字列を uint32_t のビットマスクにエンコードしています。
- A を 0、B を 1 - 位置 \(i\) の文字をビット \(i\) で管理

これにより、回転やパターン複製をビット演算中心で実装でき、定数倍が軽くなります。

操作の扱い

• 左回転・右回転：ビットシフトで1手で計算
• パターン複製：\(d \mid N,\, d<N\) を選び、先頭 \(d\) ビットを周期として全長に繰り返す

BFS中に未訪問状態だけキューへ入れることで、最初に \(T\) に到達した距離が最小操作回数になります。
最後まで到達しなければ -1 です。

アルゴリズム

1. 入力を受け取る。\(S=T\) なら 0 を出力して終了。
2. \(S, T\) をビットマスクに変換。
3. \(N\) の真の約数 \(d\)（\(1 \le d < N,\, N \bmod d=0\)）を列挙。
4. BFS を実行：
   • 現在状態 cur から
     • 左回転状態
     • 右回転状態
     • 各 \(d\) に対するパターン複製状態 を生成
   • 未訪問なら距離 +1 で登録してキューへ
   • 生成時に目標 goal と一致したら即出力して終了
5. BFS終了まで見つからなければ -1 を出力。

計算量

状態数を \(M\)（\(S\) から到達した状態数）とし、真の約数の個数を \(\tau(N)-1\) とします。

• 1状態あたりの遷移数は \(2 + (\tau(N)-1)\)
• ただしパターン複製1回の生成に \(O(N)\) かかる実装なので、全体ではおおむね
  時間計算量: \(O\!\left(M \cdot (\tau(N)\cdot N)\right)\)
  （\(N \le 25\) なので十分実用的）
• 空間計算量: \(O(M)\)（dist とキュー）

実装のポイント

• N<=25 なので uint32_t で安全に全ビットを保持できる。

• ビット \(i\) を「文字列の位置 \(i\)」に対応させると、複製操作 src = i % d が書きやすい。

• BFS の訪問管理は unordered_map<uint32_t,int>（または unordered_set + 配列距離）で行い、未訪問判定を高速化。

• 目標状態は「キューから取り出したとき」ではなく「生成した瞬間」に判定すると少し速い。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S, T;
    cin >> N >> S >> T;

    if (S == T) {
        cout << 0 << '\n';
        return 0;
    }

    // Enumerate all binary strings of length N as states (N<=25).
    // BFS from S with operations:
    // 1) left rotation
    // 2) right rotation
    // 3) pattern copy for any divisor d of N, d < N

    // Encode string as uint32_t bitmask, bit i = 1 if s[i]=='B'
    auto encode = [&](const string& s) -> uint32_t {
        uint32_t x = 0;
        for (int i = 0; i < N; i++) {
            if (s[i] == 'B') x |= (1u << i);
        }
        return x;
    };

    auto left_rot = [&](uint32_t x) -> uint32_t {
        uint32_t first = x & 1u;
        x >>= 1;
        if (first) x |= (1u << (N - 1));
        return x;
    };

    auto right_rot = [&](uint32_t x) -> uint32_t {
        uint32_t last = (x >> (N - 1)) & 1u;
        x = ((x << 1) & ((N == 32) ? 0xFFFFFFFFu : ((1u << N) - 1u)));
        if (last) x |= 1u;
        return x;
    };

    vector<int> divisors;
    for (int d = 1; d < N; d++) {
        if (N % d == 0) divisors.push_back(d);
    }

    auto replicate = [&](uint32_t x, int d) -> uint32_t {
        // Take prefix length d and repeat N/d times
        uint32_t res = 0;
        for (int i = 0; i < N; i++) {
            int src = i % d;
            uint32_t bit = (x >> src) & 1u;
            res |= (bit << i);
        }
        return res;
    };

    uint32_t start = encode(S);
    uint32_t goal = encode(T);

    unordered_map<uint32_t, int> dist;
    dist.reserve(1 << 20);
    queue<uint32_t> q;

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

    while (!q.empty()) {
        uint32_t cur = q.front(); q.pop();
        int cd = dist[cur];

        uint32_t n1 = left_rot(cur);
        if (!dist.count(n1)) {
            dist[n1] = cd + 1;
            if (n1 == goal) {
                cout << cd + 1 << '\n';
                return 0;
            }
            q.push(n1);
        }

        uint32_t n2 = right_rot(cur);
        if (!dist.count(n2)) {
            dist[n2] = cd + 1;
            if (n2 == goal) {
                cout << cd + 1 << '\n';
                return 0;
            }
            q.push(n2);
        }

        for (int d : divisors) {
            uint32_t n3 = replicate(cur, d);
            if (!dist.count(n3)) {
                dist[n3] = cd + 1;
                if (n3 == goal) {
                    cout << cd + 1 << '\n';
                    return 0;
                }
                q.push(n3);
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}

---

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