概要

条件を満たす \(01\) 文字列を部屋とみなし、現在の部屋から「未訪問の隣接部屋のうち部屋番号が最小の部屋」へ貪欲に移動していきます。
この巡回をそのままシミュレーションし、文字列 \(t\) に到達する移動回数を求めます。

考察

まず重要なのは、これは最短経路問題ではないという点です。
高橋君は戻って探索を続けることはせず、毎回「今いる部屋から行ける未訪問の部屋のうち、部屋番号が最小の部屋」へだけ進みます。
したがって、BFS や DFS で到達可能性や最短距離を求める問題ではなく、決められたルールに従って一本道の巡回をシミュレーションする問題です。

---

部屋番号は、条件を満たす文字列を辞書順に並べた順番です。
ただし、同じ長さの \(01\) 文字列では、辞書順は二進数として見たときの大小関係と一致します。

例えば、

\[ 001 < 010 < 100 \]

であり、これは二進数としても

\[ 1 < 2 < 4 \]

です。

そのため、各文字列を整数として扱えば、部屋番号そのものを計算しなくても「どちらの部屋番号が小さいか」を比較できます。

---

現在の文字列を整数 \(x\) とします。
隣接する部屋は、\(x\) のどれか \(1\) bit を反転したものです。

候補の中で最も部屋番号が小さいものを探すには、以下の順で調べればよいです。

1. 1 を 0 に変える候補

1 を 0 に変えると、整数値は小さくなります。
一方、0 を 1 に変えると整数値は大きくなります。

したがって、使える候補があるなら、まず 1 を 0 に変える候補の中から選ぶべきです。

さらに、より上位の bit を 1 から 0 に変えるほど、大きく値が減ります。
つまり、最も小さい候補から順に調べるには、左側の bit から順に 1 を 0 に変えればよいです。

2. 0 を 1 に変える候補

1 を 0 に変える候補が使えなかった場合だけ、0 を 1 に変える候補を調べます。

この場合は整数値が増えますが、なるべく小さく増やしたいので、下位 bit から順に 0 を 1 に変えます。

---

ただし、反転後の文字列が以下の条件を満たす必要があります。

• まだ訪問していない
• 000 または 111 を含まない

この条件を満たす最初の候補が、次に移動する部屋になります。

素朴に全 \(2^N\) 個の文字列を列挙すると、\(N = 26\) では約 \(6700\) 万個あり重いです。
しかし、実際に必要なのは「現在地から次に行く部屋」を探すことだけなので、各ステップで高々 \(N\) 個の bit 反転を試せば十分です。

アルゴリズム

文字列を整数に変換して扱います。

• cur : 現在いる部屋
• target : 目的の部屋
• visited : 訪問済みの部屋集合
• steps : 移動回数

まず、\(s = t\) なら答えは \(0\) です。

そうでない場合、以下を繰り返します。

1. 次に移動する部屋 nxt を未定にする
2. 上位 bit から順に見て、現在 1 である bit を反転する
   • 反転後が未訪問
   • 000 も 111 も含まない
     なら、その部屋を nxt として採用する
3. 見つからなければ、下位 bit から順に見て、現在 0 である bit を反転する
   • 同様に、未訪問かつ条件を満たすなら採用する
4. それでも見つからなければ巡回終了なので、\(-1\) を出力する
5. nxt へ移動し、移動回数を \(1\) 増やす
6. target に到達したなら、その移動回数を出力する
7. そうでなければ visited に追加して続ける

---

条件判定は bit 演算で高速に行います。

ある整数 y が 111 を含むかどうかは、

y & (y >> 1) & (y >> 2)

が \(0\) でないかを見れば判定できます。

これは、ある位置から連続する \(3\) bit がすべて 1 なら、その位置の bit が AND 後にも残るためです。

000 を含むかどうかは、\(N\) bit の範囲で 0 と 1 を反転した値を作り、それに対して同じ判定をします。

z = full ^ y

ここで、

full = (1 << N) - 1

です。

z に 111 が含まれるなら、元の y には 000 が含まれています。

計算量

巡回で実際に訪れる部屋数を \(M\) とします。

各ステップで高々 \(N\) 個程度の bit 反転候補を調べ、それぞれの妥当性判定は bit 演算で \(O(1)\) です。

• 時間計算量: \(O(MN)\)
• 空間計算量: \(O(M)\)

ここで \(M\) は条件を満たす文字列数以下です。
条件を満たす文字列数は Fibonacci 数程度で、\(N \leq 26\) では十分小さいです。

実装のポイント

• 長さ \(N\) の文字列を int(s, 2) で整数に変換します。

• 左端の文字は上位 bit に対応します。

• 1 を 0 にする候補は、上位 bit から調べます。

• 0 を 1 にする候補は、下位 bit から調べます。

• Python の ~y は無限長の補数表現になるため、\(N\) bit だけを反転したい場合は full ^ y を使います。

• 出発地点は最初から訪問済みなので、visited = {cur} で開始します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    s = input().strip()
    t = input().strip()

    cur = int(s, 2)
    target = int(t, 2)

    if cur == target:
        print(0)
        return

    full = (1 << N) - 1
    desc_masks = [1 << k for k in range(N - 1, -1, -1)]
    asc_masks = [1 << k for k in range(N)]

    visited = {cur}
    steps = 0

    while True:
        nxt = -1

        for m in desc_masks:
            if cur & m:
                y = cur ^ m
                if y not in visited:
                    if not (y & (y >> 1) & (y >> 2)):
                        z = full ^ y
                        if not (z & (z >> 1) & (z >> 2)):
                            nxt = y
                            break

        if nxt == -1:
            for m in asc_masks:
                if not (cur & m):
                    y = cur ^ m
                    if y not in visited:
                        if not (y & (y >> 1) & (y >> 2)):
                            z = full ^ y
                            if not (z & (z >> 1) & (z >> 2)):
                                nxt = y
                                break

        if nxt == -1:
            print(-1)
            return

        steps += 1
        cur = nxt

        if cur == target:
            print(steps)
            return

        visited.add(cur)

if __name__ == "__main__":
    main()

---

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