AtCoder Grand Contest 031 C - Differ by 1 Bit

C - Differ by 1 Bit

Submission #4602092 - AtCoder Grand Contest 031

snukeさんのコードを参考にしました。

方針は解説生放送と同じです。

解法

まず遷移は奇数回なので、aとbの立っているbitの数が偶数差ならNO。

それ以外の場合はYES。（証明できないが）

nが1~3の時のグラフを描く

グラフはn次元超立方体になり、xyz....軸は、変化したbitの桁に対応している。

また、n次元のグラフは漸化的に作れる。

n-1次元のグラフを二つ用意して、nビット目の辺で結んでやればいい↓。

今回の解法はその逆操作で、n次元のグラフを二つのn-1次元に分解する事を繰り返して、1次元に帰着させて解く。

↓赤線で分解し、数字を中継地点として部分問題を解いている

具体的に分解する物

sとtのxorを取ると、sからtへ移動する際に変化する必要があるbitが分かる。

その中のあるビットの軸（上でビットの変化をxyz軸のように対応させた）を切断してグラフを二つに分けると、sとtを分離させることができる。

分解する方法

今までに分解したbitの集合を持ち、その方向へは動かないようにすれば分解したことになる。

Submission #4615397 - AtCoder Grand Contest 031

int n, a, b;
vi res;

//最下位ビット
int lbit(int n) {
    return n & -n;
}
//最上位ビット
int hbit(int n) {
    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);
    n |= (n >> 32);
    return n - (n >> 1);
}
#define bcou __builtin_popcountll

void dfs(int s, int t, int cuts) {
    //t以外に行ける場所がない
    if (bcou(cuts) == n - 1) {
        res.pb(s);
        res.pb(t);
        return;
    }
    //s -> t で使うことになる軸の集合
    int need = s ^t;
    //needに含まれる軸ncutで切断すれば、sとtを分離できる
    int ncut = lbit(need);
    cuts |= ncut;
    //sとtを分離した時、s側で使える軸の集合
    int cand = ((1 << n) - 1) ^cuts;
    int mid = s ^lbit(cand);
    //t側のスタート地点がtになってはいけない
    if ((mid ^ ncut) == t) {
        mid = s ^ hbit(cand);
    }
    //二つの部分問題に帰着できた
    dfs(s, mid, cuts);
    //ncutでsとtを分離したため、mid^ncutでt側に移動できる
    dfs(mid ^ ncut, t, cuts);
}

void solve() {
    cin >> n >> a >> b;
    if (bcou(a ^ b)%2 == 0) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    dfs(a, b, 0);
    cout << res << endl;
}