概要

「同じ文字が3連続しない」長さ \(N\) の01文字列を辞書順に並べたものを部屋とし、1文字違いの部屋同士が通路で結ばれたグラフ上で、貪欲に部屋番号の小さい未訪問隣接部屋へ移動するシミュレーションを行い、目標の部屋への到達ステップ数を求める問題です。

考察

有効な文字列の数

「同じ文字が3つ以上連続しない」長さ \(N\) の文字列の個数を \(f(N)\) とすると、\(f(N) = f(N-1) + f(N-2)\)（フィボナッチ型の漸化式）が成り立ちます。\(f(1) = 2, f(2) = 4\) で、\(N = 26\) のとき \(f(26) = 392{,}836\) 程度です。これは全列挙可能なサイズです。

部屋番号の決定

有効な文字列を辞書順に並べたときのインデックスがそのまま部屋番号になります。辞書順に生成すれば、配列の添字が部屋番号に対応します。

隣接関係

文字列の各位置を1つ反転してみて、結果が有効（3連続しない）であれば通路で結ばれています。反転後の有効性は、反転位置の前後2文字を見るだけで \(O(1)\) で判定できます。

巡回のシミュレーション

「未訪問の隣接部屋のうち部屋番号最小のものへ移動」というルールは、バックトラックなしの単純な貪欲探索です。各部屋の隣接リストをあらかじめ部屋番号の昇順にソートしておけば、先頭から走査して最初の未訪問を選ぶだけで済みます。

アルゴリズム

1. 有効文字列の全列挙: 再帰的に辞書順で全有効文字列を生成し、配列 valid に格納する。
2. 文字列→インデックスの対応: ハッシュマップで各文字列から配列中のインデックス（＝部屋番号−1）を引けるようにする。
3. 隣接リストの構築: 各文字列について全 \(N\) 箇所を反転し、有効なら対応するインデックスを隣接リストに追加。リストを昇順ソート。
4. 貪欲シミュレーション: 出発部屋から開始し、各ステップで隣接リストを先頭から走査して最初の未訪問部屋へ移動。目標部屋に到達したらステップ数を出力、行き止まりなら \(-1\) を出力。

計算量

• 時間計算量: \(O(M \cdot N \log N)\)（隣接リスト構築のソート部分が支配的。シミュレーション本体は \(O(M \cdot N)\)。ここで \(M \approx 392{,}836\), \(N \leq 26\)）
• 空間計算量: \(O(M \cdot N)\)（隣接リストの格納）

実装のポイント

• 辞書順生成: 再帰で '0' → '1' の順にappendすると自然に辞書順になる。直前2文字と一致するかだけチェック。

• 反転の有効性判定: 位置 \(j\) を反転したとき、\(j-2, j-1, j, j+1, j+2\) の範囲で3連続が発生しないかを確認する（3パターンのチェック）。

• ハッシュマップの活用: 反転後の文字列が有効かどうかを先に局所的に判定し、有効なときだけハッシュマップで索引を引くことで効率化。

• visited配列: vector<bool> で各部屋の訪問状態を管理。シミュレーションは最悪 \(M\) ステップで終了するため十分高速。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    string s, t;
    cin >> N >> s >> t;
    
    // Generate all valid strings in lexicographic order
    vector<string> valid;
    valid.reserve(300000);
    function<void(string&)> generate = [&](string& cur) {
        if ((int)cur.size() == N) {
            valid.push_back(cur);
            return;
        }
        for (char c : {'0', '1'}) {
            int len = cur.size();
            if (len >= 2 && cur[len-1] == c && cur[len-2] == c) continue;
            cur.push_back(c);
            generate(cur);
            cur.pop_back();
        }
    };
    string empty = "";
    generate(empty);
    
    int M = valid.size();
    
    // Map string to index using hash map
    unordered_map<string, int> str_to_idx;
    str_to_idx.reserve(M * 2);
    for (int i = 0; i < M; i++) {
        str_to_idx[valid[i]] = i;
    }
    
    int start = str_to_idx[s];
    int target = str_to_idx[t];
    
    if (start == target) {
        cout << 0 << endl;
        return 0;
    }
    
    // For each room, compute sorted list of neighbor indices
    vector<vector<int>> neighbors(M);
    for (int i = 0; i < M; i++) {
        string& str = valid[i];
        for (int j = 0; j < N; j++) {
            char orig = str[j];
            char flipped = (orig == '0') ? '1' : '0';
            // Check validity of flipping position j
            bool ok = true;
            if (j >= 2 && flipped == str[j-1] && flipped == str[j-2]) ok = false;
            if (ok && j >= 1 && j < N-1 && flipped == str[j-1] && flipped == str[j+1]) ok = false;
            if (ok && j < N-2 && flipped == str[j+1] && flipped == str[j+2]) ok = false;
            if (ok) {
                str[j] = flipped;
                auto it = str_to_idx.find(str);
                if (it != str_to_idx.end()) {
                    neighbors[i].push_back(it->second);
                }
                str[j] = orig;
            }
        }
        sort(neighbors[i].begin(), neighbors[i].end());
    }
    
    // Simulate the greedy walk
    vector<bool> visited(M, false);
    int current = start;
    visited[current] = true;
    int steps = 0;
    
    while (true) {
        int next = -1;
        for (int nb : neighbors[current]) {
            if (!visited[nb]) {
                next = nb;
                break;
            }
        }
        if (next == -1) {
            cout << -1 << endl;
            return 0;
        }
        steps++;
        visited[next] = true;
        current = next;
        if (current == target) {
            cout << steps << endl;
            return 0;
        }
    }
}

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