はまやんはまやんはまやん

hamayanhamayan's blog

Differ by 1 Bit [AtCoder Grand Contest 031 C]

競技プログラミング

https://atcoder.jp/contests/agc031/tasks/agc031_c

解法

https://atcoder.jp/contests/agc031/submissions/4606271

！！注意！！もっとスマートな解法があります！！

まず、"NO"となるのは、AとBで立っているビット数のパリティが一致しているとき。
まずパリティが一致していると駄目なのは、二部グラフっぽく見ると分かる。
これが必要条件な理由は分からない。AC証明した。
　
さて、問題が構築だが、以下の関数を用いて、根性で構築する。
go1(L,R,from,len) := [L,R)の区間でfromを始点として一筆書きした時の終点を返す
go2(L,R,from,to,len) := [L,R)の区間でfromとtoを始点として、それぞれ一筆書きした時の終点を2つ返す
connect2(L,R,from,to,len) := [L,R)の区間でfromとtoをつなぐ、一筆書きをする
これが正しく作れれば、connect2(0,1＜＜N,A,B,1＜＜N)で答えが求まる。
上記の関数内では、辺を作りながら、処理を進めている。
以下、中心C=(L+R)/2を説明に使う。
　
connect2関数

  • [L,C)にfromもtoもある場合
    • [L,C)の区間でgo2関数を使って、2本の一筆書きをする
    • それぞれの一筆書きの終点を[C,R)に伸ばして、[C,R)でconnect2関数をやる
  • [C,R)にfromもtoもある場合
    • 同様
  • [L,C)にfrom, [C,R)にtoがある場合
    • 2つの区間をつなぐiとi+len/2間の辺を決めて、connect2関数で、fromとi, i+len/2とtoをつなぐ

　
go1関数

  • [L,C)にfromがある場合
    • [L,C)でgo1関数をやって、でてきた終点から、[C,R)に辺を張って、改めて、go1関数をする
  • [C,R)にfromがある場合
    • 同様

　
go2関数

  • [L,C)にfromもtoもある場合
    • [L,C)の区間でgo2関数を使って、2本の一筆書きをする
    • それぞれの一筆書きの終点を[C,R)に伸ばして、[C,R)でgo2関数をやる
  • [C,R)にfromもtoもある場合
    • 同様
  • [L,C)にfrom, [C,R)にtoがある場合
    • それぞれの区間でgo1関数をやる

　
こうするとグラフが出来上がるので、ここから数列作ると答え。

int N, A, B;
vector<int> E[1 << 17];
//---------------------------------------------------------------------------------------------------
void add(int a, int b) {
    E[a].push_back(b);
    E[b].push_back(a);
}
//---------------------------------------------------------------------------------------------------
void connect2(int L, int R, int from, int to, int len);
int go1(int L, int R, int from, int len) {
    if (len == 1) return from;
    else if (len == 2) {
        if (L == from) {
            add(L + 1, from);
            return L + 1;
        }
        else {
            add(L, from);
            return L;
        }
    }
 
    int C = (L + R) / 2;
 
    // 上にある
    if (from < C) {
        rep(i, L, C) if (i != from) {
            if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
                connect2(L, C, min(from,i), max(from,i), len / 2);
 
                add(i, i + len / 2);
 
                return go1(C, R, i + len / 2, len / 2);
            }
        }
    }
 
    // 下にある
    if (C <= from) {
        rep(i, C, R) if (i != from) {
            if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
                connect2(C, R, min(from, i), max(from, i), len / 2);
 
                add(i, i - len / 2);
 
                return go1(L, C, i - len / 2, len / 2);
            }
        }
    }
}
pair<int, int> go2(int L, int R, int from, int to, int len) {
    if (len == 2) return { from, to };
 
    int C = (L + R) / 2;
 
    // 上に2つともある
    if (to < C) {
        auto p = go2(L, C, from, to, len / 2);
 
        add(p.first, p.first + len / 2);
        add(p.second, p.second + len / 2);
 
        return go2(C, R, p.first + len / 2, p.second + len / 2, len / 2);
    }
 
    // 下に2つともある
    if (C <= from) {
        auto p = go2(C, R, from, to, len / 2);
 
        add(p.first, p.first - len / 2);
        add(p.second, p.second - len / 2);
 
        return go2(L, C, p.first - len / 2, p.second - len / 2, len / 2);
    }
 
    return { go1(L, C, from, len / 2), go1(C, R, to, len / 2) };
}
void connect2(int L, int R, int from, int to, int len) {
    if (len == 2) {
        add(from, to);
        return;
    }
 
    int C = (L + R) / 2;
 
    // 上に2つともある
    if (to < C) {
        auto p = go2(L, C, from, to, len / 2);
 
        add(p.first, p.first + len / 2);
        add(p.second, p.second + len / 2);
 
        connect2(C, R, p.first + len / 2, p.second + len / 2, len / 2);
        return;
    }
 
    // 下に2つともある
    if (C <= from) {
        auto p = go2(C, R, from, to, len / 2);
 
        add(p.first, p.first - len / 2);
        add(p.second, p.second - len / 2);
 
        connect2(L, C, p.first - len / 2, p.second - len / 2, len / 2);
        return;
    }
 
    rep(i, L, C) if(i != from and i + len / 2 != to) {
        if (__builtin_popcount(i) % 2 != __builtin_popcount(from) % 2) {
 
            add(i, i + len / 2);
 
            connect2(L, C, min(i, from), max(i, from), len / 2);
            connect2(C, R, min(i + len/2, to), max(i + len/2, to), len / 2);
            return;
        }
    }
}
//---------------------------------------------------------------------------------------------------
int vis[1 << 17];
vector<int> ans;
void dfs(int cu) {
    ans.push_back(cu);
    vis[cu] = 1;
    fore(to, E[cu]) if (!vis[to]) dfs(to);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;
 
    if (__builtin_popcount(A) % 2 == __builtin_popcount(B) % 2) {
        printf("NO\n");
        return;
    }
 
    int isSwap = 0;
    if (A > B) {
        swap(A, B);
        isSwap = 1;
    }
 
    connect2(0, 1 << N, A, B, 1 << N);
    dfs(A);
 
    printf("YES\n");
 
    if (isSwap) reverse(all(ans));
 
    rep(i, 0, 1 << N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}