概要

長さ \(N\) の条件を満たす 01 文字列を部屋とみなし、指定されたルールに従って「未訪問の隣接部屋のうち部屋番号が最小のもの」へ移動し続けます。
この巡回は分岐しない一本道なので、実際にその順番をシミュレーションすればよいです。

考察

各部屋は長さ \(N\) の 01 文字列です。
これを \(N\) ビットの整数として扱うと便利です。

例えば \(N=3\) のとき、

• 001 \(\rightarrow 1\)
• 010 \(\rightarrow 2\)
• 011 \(\rightarrow 3\)
• 100 \(\rightarrow 4\)

のように対応させます。

ここで重要なのは、長さが同じ 01 文字列では、辞書順と整数としての大小関係が一致することです。
つまり、部屋番号そのものを計算しなくても、候補の中で整数値が最小のものを選べば「部屋番号が最小」の部屋を選んだことになります。

ただし、すべての \(2^N\) 個の文字列が部屋として存在するわけではありません。
000 や 111 のように、同じ文字が \(3\) 個以上連続する文字列は無効です。

そのため、あらかじめ各ビット列が有効な部屋かどうかを valid 配列で管理しておきます。

また、この問題は通常の BFS や DFS で到達可能性を調べる問題ではありません。
高橋君は戻って探索を続けることはせず、毎回決められたルールでただ 1 つの部屋へ進みます。
したがって、実際の移動をそのままシミュレーションする必要があります。

アルゴリズム

まず、文字列 \(s, t\) をそれぞれ整数のビットマスクに変換します。

• start: 出発する部屋
• target: 目標の部屋

もし start == target なら、出発時点ですでに訪問済みなので答えは \(0\) です。

次に、有効な部屋をすべて列挙します。

DFS で左から順に文字を決めていきます。

状態として以下を持ちます。

• pos: 何文字目まで決めたか
• last: 直前の文字
• run: 直前の文字が何個連続しているか
• mask: 現在までに作ったビット列

次に置く文字 b が last と同じで、すでに run == 2 なら、同じ文字が \(3\) 個連続してしまうので置けません。
それ以外の場合だけ再帰的に進めます。

長さ \(N\) まで作れたら、その mask を有効な部屋として valid[mask] = true にします。

その後、巡回をシミュレーションします。

現在の部屋を cur とします。
cur から 1 ビットだけ反転したものが隣接する可能性のある部屋です。

各ビット位置 bit について、

nxt = cur ^ (1 << bit)

とすると、cur の bit 番目だけを反転した部屋になります。

この nxt について、

• 有効な部屋である
• まだ訪問していない

なら移動候補です。

その中で整数値が最小のものを選びます。
これは辞書順最小、すなわち部屋番号最小の部屋を選ぶことに対応します。

移動先が存在しなければ巡回終了です。
移動するたびに移動回数を増やし、もし target に到達したらその回数を出力します。

最後まで target に到達しなければ \(-1\) を出力します。

計算量

有効な部屋の個数を \(V\) とします。
同じ文字が \(3\) 個連続しない 01 文字列の個数はフィボナッチ数程度で、\(V = O(\varphi^N)\) です。

• 有効な部屋の列挙: \(O(V)\)
• 巡回のシミュレーション: 各部屋で最大 \(N\) 個の隣接候補を見るので \(O(NV)\)
• 配列の初期化: \(O(2^N)\)

したがって、

• 時間計算量: \(O(2^N + NV)\)
• 空間計算量: \(O(2^N)\)

です。

\(N \leq 26\) なので、\(2^N\) サイズの配列を用意しても間に合います。

実装のポイント

• 文字列は左から順にビットを詰めて整数に変換します。

• 長さが固定なので、01 文字列の辞書順と整数の大小は一致します。

• 部屋番号の実際の値を求める必要はありません。

• 隣接部屋は cur ^ (1 << bit) で求められます。

• 未訪問の有効な隣接部屋の中から、整数値が最小のものを選びます。

• 巡回は戻らないので、BFS や DFS ではなく、ルール通りに一本道をシミュレーションします。

  ソースコード

#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 toMask = [&](const string& x) {
        int m = 0;
        for (char c : x) m = (m << 1) | (c - '0');
        return m;
    };

    int start = toMask(s);
    int target = toMask(t);

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

    int M = 1 << N;
    vector<unsigned char> valid(M, 0), visited(M, 0);

    auto dfs = [&](auto&& self, int pos, int last, int run, int mask) -> void {
        if (pos == N) {
            valid[mask] = 1;
            return;
        }
        for (int b = 0; b <= 1; b++) {
            if (b == last && run == 2) continue;
            self(self, pos + 1, b, (b == last ? run + 1 : 1), (mask << 1) | b);
        }
    };

    dfs(dfs, 0, -1, 0, 0);

    int cur = start;
    visited[cur] = 1;
    int moves = 0;

    while (true) {
        int best = -1;

        for (int bit = 0; bit < N; bit++) {
            int nxt = cur ^ (1 << bit);
            if (valid[nxt] && !visited[nxt]) {
                if (best == -1 || nxt < best) best = nxt;
            }
        }

        if (best == -1) break;

        cur = best;
        visited[cur] = 1;
        moves++;

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

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

---

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