概要

長さ \(N\) の A/B 文字列を状態とみなし、3 種類の操作で遷移できるグラフ上で、\(S\) から \(T\) への最短距離を求める問題です。
すべての操作のコストは \(1\) なので、幅優先探索（BFS）で最小操作回数を求めます。

考察

操作列は何回でも行えるため、単純に「何手目まで全探索する」と考えると、同じ状態に何度も戻ることがあり、探索が無限に続く可能性があります。

しかし、ビーズ列は長さ \(N\) の A/B 文字列なので、取りうる状態数は高々

\(2^N\)

通りです。制約は \(N \leq 25\) なので、全状態をグラフの頂点として扱うことができます。

各状態からできる操作は次の通りです。

• 左に回転
• 右に回転
• \(N\) の正の約数 \(d\)（\(d < N\)）ごとに、先頭 \(d\) 文字を繰り返す

すべての操作はコスト \(1\) なので、BFS を使えば最初に \(T\) に到達したときの距離が最小操作回数になります。

また、文字列をそのまま扱うと回転や比較に \(O(N)\) かかります。
そこで、A を 0、B を 1 として整数のビット列にエンコードします。

例えば、文字列 ABBA は次のように表せます。

• A \(\rightarrow 0\)
• B \(\rightarrow 1\)

各文字をビットとして持てば、回転や先頭 \(d\) 文字の取り出しをビット演算で高速に行えます。

アルゴリズム

まず、文字列 \(S, T\) を整数に変換します。

文字列の \(i\) 文字目が B なら、整数の第 \(i\) ビットを \(1\) にします。

if (s[i] == 'B') v |= (1 << i);

これにより、長さ \(N\) の文字列は \(0\) 以上 \(2^N - 1\) 以下の整数として表せます。

次に、BFS を行います。

状態 \(x\) に対して、次の遷移を作ります。

左回転

先頭文字、つまり第 \(0\) ビットを末尾、第 \(N-1\) ビットに移動します。

int leftRot = (x >> 1) | ((x & 1) << (N - 1));

右回転

末尾文字、つまり第 \(N-1\) ビットを先頭、第 \(0\) ビットに移動します。

int rightRot = ((x << 1) & fullMask) | (x >> (N - 1));

ここで fullMask = (1 << N) - 1 として、不要な上位ビットを消しています。

パターン複製

\(d\) を \(N\) の正の約数、かつ \(d < N\) とします。

現在の状態 \(x\) の先頭 \(d\) 文字は、下位 \(d\) ビットです。

int pattern = x & ((1 << d) - 1);

このパターンを \(N/d\) 回繰り返した文字列を作ります。

例えば、\(N = 6, d = 2\) で先頭パターンが AB なら、結果は

ABABAB

になります。

コードでは、この変換を毎回計算すると遅くなるため、あらかじめ repeatTable に前計算しています。

table[p] = p を長さ N まで繰り返した状態

BFS では、未訪問の状態に到達したら距離を記録します。

dist[y] = dist[x] + 1;

もしその状態が目標 target なら、その距離を出力して終了します。

BFS が終わっても target に到達できなければ、-1 を出力します。

計算量

\(D\) を \(N\) の正の約数 \(d < N\) の個数とします。

各状態から調べる遷移は、左回転・右回転・各 \(d\) に対するパターン複製なので \(O(D + 2)\) 個です。

• 時間計算量: \(O(2^N \cdot D)\)
• 空間計算量: \(O(2^N)\)

実装のポイント

• 文字列を整数のビット列として表すことで、状態の比較や回転を高速にできます。

• BFS では dist[state] == -1 を未訪問として管理します。

• パターン複製は約数 \(d\) ごとに事前計算しておくと、BFS 中は表を引くだけで済みます。

• \(S = T\) の場合は最初に 0 を出力して終了します。

  ソースコード

#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;

    auto encode = [&](const string& s) {
        int v = 0;
        for (int i = 0; i < N; i++) {
            if (s[i] == 'B') v |= (1 << i);
        }
        return v;
    };

    int start = encode(S);
    int target = encode(T);

    if (start == target) {
        cout << 0 << '\n';
        return 0;
    }

    int total = 1 << N;
    int fullMask = total - 1;

    vector<int> prefixMasks;
    vector<vector<int>> repeatTable;

    for (int d = 1; d < N; d++) {
        if (N % d != 0) continue;

        int sz = 1 << d;
        vector<int> table(sz, 0);

        for (int p = 0; p < sz; p++) {
            int v = 0;
            for (int pos = 0; pos < N; pos += d) {
                v |= (p << pos);
            }
            table[p] = v;
        }

        prefixMasks.push_back(sz - 1);
        repeatTable.push_back(move(table));
    }

    vector<int> dist(total, -1);
    vector<int> q;
    q.reserve(total);

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

    auto push_state = [&](int y, int nd) -> bool {
        if (dist[y] != -1) return false;
        dist[y] = nd;
        if (y == target) {
            cout << nd << '\n';
            return true;
        }
        q.push_back(y);
        return false;
    };

    for (size_t head = 0; head < q.size(); head++) {
        int x = q[head];
        int nd = dist[x] + 1;

        int leftRot = (x >> 1) | ((x & 1) << (N - 1));
        if (push_state(leftRot, nd)) return 0;

        int rightRot = ((x << 1) & fullMask) | (x >> (N - 1));
        if (push_state(rightRot, nd)) return 0;

        for (size_t i = 0; i < repeatTable.size(); i++) {
            int y = repeatTable[i][x & prefixMasks[i]];
            if (push_state(y, nd)) return 0;
        }
    }

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

---

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