概要

長さ \(N\)（\(N \leq 25\)）のビーズ列に対し、巡回左シフト・巡回右シフト・パターン複製の3種類の操作を使って、初期状態 \(S\) から目標状態 \(T\) へ到達する最小操作回数を求める問題です。状態空間をBFS（幅優先探索）で探索することで解けます。

考察

• ビーズ列は A と B の2種類の文字のみで構成され、長さは最大25です。したがって、ビーズ列の状態は最大で \(2^{25} = 33{,}554{,}432\) 通りしかありません。
• 「最小操作回数」を求める問題なので、各状態を頂点、各操作を辺としたグラフ上の最短経路問題と捉えることができます。辺の重みはすべて1なので、BFSが最適です。
• 各状態からの遷移先は、左回転で1つ、右回転で1つ、パターン複製で（\(N\) の真の約数の個数）個の合計 \(O(\sqrt{N})\) 程度であり、少数です。
• \(N \leq 25\) なので、各状態をビット列（整数）で表現できます。例えば A を 0、B を 1 として、長さ \(N\) の文字列を \(N\) ビットの整数に対応させます。

アルゴリズム

1. 状態のビット表現: 文字列を整数に変換します。先頭文字が最上位ビットに対応します。
2. 前処理: \(N\) の正の約数で \(N\) 未満のものをすべて列挙しておきます。
3. BFS: 初期状態 \(S\) からBFSを開始し、各状態について以下の遷移を試みます：
   • 左回転: ビット列を1ビット左にシフトし、溢れたビットを最下位に入れる。 ((u << 1) & mask) | (u >> (N-1))
   • 右回転: ビット列を1ビット右にシフトし、溢れたビットを最上位に入れる。 (u >> 1) | ((u & 1) << (N-1))
   • パターン複製: 各約数 \(d\) について、上位 \(d\) ビット（先頭 \(d\) 文字に対応）を取り出し、それを \(N/d\) 回繰り返した整数を作る。
4. 目標状態 \(T\) に到達したら、その時点のステップ数を出力します。BFSが終了しても到達できなければ -1 を出力します。

具体例: \(N = 4\), \(S = \) ABAB（= 0101 = 5）, \(T = \) AAAA（= 0000 = 0）の場合 - 左回転: ABAB → BABA - パターン複製(\(d=2\)): ABAB → 先頭2文字 AB を2回繰り返し → ABAB（変わらない） - パターン複製(\(d=1\)): ABAB → 先頭1文字 A を4回繰り返し → AAAA（目標！）

よって1回の操作で到達可能です。

計算量

• 時間計算量: \(O(2^N \cdot d(N))\)（\(d(N)\) は \(N\) の約数の個数。各状態を高々1回訪問し、各状態から \(O(d(N))\) 個の遷移を調べる）
• 空間計算量: \(O(2^N)\)（訪問済み配列とBFSキュー）

\(N = 25\) のとき \(2^{25} \approx 3.4 \times 10^7\) であり、BFSの各処理はビット演算のみで高速なため、十分間に合います。

実装のポイント

• 文字列を整数にエンコードすることで、状態の比較・保存が \(O(1)\) で行えます。

• visited 配列を \(2^N\) サイズで確保し、ハッシュマップではなく直接アクセスすることで高速に処理します。

• パターン複製の実装では、上位 \(d\) ビットを取り出すために (u >> (N - d)) & ((1 << d) - 1) を使い、それを \(N/d\) 回左シフトしながらORで連結します。

• BFSの各レベルを sz で管理することで、ステップ数を正確に追跡しています。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    string S, T;
    cin >> N >> S >> T;
    
    auto to_int = [&](const string& s) {
        int val = 0;
        for (int i = 0; i < N; i++) {
            val = (val << 1) | (s[i] == 'B' ? 1 : 0);
        }
        return val;
    };
    
    int src = to_int(S);
    int dst = to_int(T);
    
    if (src == dst) { cout << 0; return 0; }
    
    int mask = (1 << N) - 1;
    int total = 1 << N;
    
    vector<int> divisors;
    for (int d = 1; d < N; d++) {
        if (N % d == 0) divisors.push_back(d);
    }
    
    vector<bool> visited(total, false);
    visited[src] = true;
    queue<int> q;
    q.push(src);
    int steps = 0;
    
    while (!q.empty()) {
        steps++;
        int sz = q.size();
        while (sz--) {
            int u = q.front(); q.pop();
            
            auto try_add = [&](int v) -> bool {
                if (!visited[v]) {
                    if (v == dst) return true;
                    visited[v] = true;
                    q.push(v);
                }
                return false;
            };
            
            // Left rotate
            int left = ((u << 1) & mask) | ((u >> (N-1)) & 1);
            if (try_add(left)) { cout << steps; return 0; }
            
            // Right rotate
            int right = (u >> 1) | ((u & 1) << (N-1));
            if (try_add(right)) { cout << steps; return 0; }
            
            // Pattern duplication
            for (int d : divisors) {
                int pattern = (u >> (N - d)) & ((1 << d) - 1);
                int new_val = 0;
                for (int i = 0; i < N / d; i++) {
                    new_val = (new_val << d) | pattern;
                }
                if (try_add(new_val)) { cout << steps; return 0; }
            }
        }
    }
    
    cout << -1;
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。