2019-03-21

AtCoder AGC 031 C - Differ by 1 Bit (黄色, 800 点)

AtCoder AGC-C AtCoder800点数学的帰納法に基づく考察構築グレイコード 0と1の問題操作パリティ N次元空間 2^K 不変量順列を題材とした問題テク:スタートを0としてよい集合族に関する問題黄色diff 構築:数列 Yes/No判定問題直方体・立方体の問題

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。

問題へのリンク

問題概要

整数 $N, A, B$ が与えられます。 $(0, 1, ... 2^{N}−1)$ の順列 $(P_{0}, P_{1}, ... P_{2^{N}−1})$ であって、次の条件をすべて満たすものが存在するかどうか判定してください。また、存在するなら 1 つ構成してください。

$P_0 = A$
$P_{2^{N}-1} = B$
すべての $0 \le i \le 2^{N}-1$ について、 $P_{i}$ と $P_{i+1}$ は 2 進数表記でちょうど 1 桁だけ異なる。

制約

$1 \le N \le 17$

全体の overview

この問題に限らず

0-1 列の 1 点更新
順列の隣り合う要素の swap

といった辺りは、 $n$ 次元空間上の超立体において「一辺を動く」という見方をすると明快なイメージを抱けることが多い気がする。この問題もまた、0-1 な $n$ 次元空間における $n$ 次元超立方体の辺を辿っていくようなイメージの問題になっている！！！¹

またこの手の問題でよくあることとして、「スタートは 0 としてよい」というのがある。というのも出来上がる順列に対して、すべて ^ A を施しても条件を満たしていて

スタートが 0 で出来上がるものが A ^ B

なものになる。なので、0 から A ^ B を作る問題を解いて、最後に全部に ^ A をかければよい。以降、C = A ^ B とする。

さて、ひとまず $n = 2, 3, 4$ あたりで何が作れるのか実験していると

C のビットが立っている箇所が偶数なものは作れそうにない
C のビットが立っている箇所が奇数なものはすべて作れそう

ということが見えて来る。まず前者については簡単に証明できる。よくある論法で、

毎ターンごとに「ビットの立っている箇所の偶奇」が入れ替わっている

ということに着目する。ビットを立てても、ビットを消しても、どちらにしても偶奇が入れ替わっている。よって、今回は $2^{N} - 1$ 回のターンを経たあとは必ずビットカウントは奇数になる。

C のビットカウントが奇数の場合の、帰納法による証明

奇数の場合はすべてできることを示したい。こういうのは大体数学的帰納法で示せるイメージがある。そして、そうやって証明すれば大体具体的な構築方法も浮かび上がって来ることが多い気がする。

ここで、 $n$ 次元空間の超立方体を思い浮かべるとわかりやすい。例えば $n = 3$ ならば、正方形を 2 つ向かい合わせてそれぞれの頂点を結んだような図形になっていることがわかる。つまり、

$n = 3$ のときの図形は、 $n = 2$ のときの図形 × 2

である。一般に

$n$ のときの図形は、 $n-1$ のときの図形 × 2

になっていることが推測される。まず作りたいもののどこかには必ずビットが立っているので、適宜入れ替えて先頭のビットが $1$ になるようにする。すなわち $(1, ...)$ を作りたいとする。

前半戦は先頭が常に $0$ となるような、残りの $n-1$ 次元立方体について操作を行った後、先頭を $1$ にして、今度は先頭が常に $1$ の状態で残りの $n-1$ 次元立方体について操作を行うようにしてみる。

前半 (先頭が 0 の状態)

$(0, 0, 0, ..., 0)$ の状態から、先頭を $0$ に固定したまま、残りの $n-1$ 次元立方体を全部動いて最終的に一番右のビットだけ立てるようにする。

$(0, 0, 0, ..., 1)$ の状態になる

移動

1 回操作して $(1, 0, 0, ..., 1)$ の状態になる

後半 (先頭が 1 の状態)

先頭を $1$ に固定したまま、残りの $n-1$ 次元立方体を動かす。このとき、最終的に作りたいものと $(1, 0, 0, ..., 1)$ とのビット反転箇所は奇数箇所であることから、それを実現することができる。

以上より、奇数箇所のビット反転を実現できることが示された。

実装: 帰納法をそのまま再帰関数で

上の帰納法的証明をそのまま再帰関数に投げる方針。とにかく何も考えずに

// 0, 1, ..., n-1 ビット目を動かして、a を b にする
vector<int> func(int n, int a, int b);

という関数を作ってしまえば良さそう。すべてを再帰関数に委ねる！！！

ここでスタートを 0 にしないのは、やはり最上位ビットが 0 でないときは最上位に 1 を運んで来るような処理だけはしておきたくて、そうするとスタートが 0 でない形を一般的に扱えた方が嬉しい。

#include <iostream>
#include <vector>
using namespace std;

// a の i ビット目と j ビット目を swap する
void swa(int &a, int i, int j) {
    if ( (a & (1<<i)) && !(a & (1<<j)) ) a += -(1<<i) + (1<<j);
    else if ( !(a & (1<<i)) && (a & (1<<j)) ) a += (1<<i) - (1<<j);
}

// 0, 1, ..., n-1 ビット目を動かして、a を b にする
vector<int> solve(int n, int a, int b) {
    if (n == 1) return {a, b};
    
    // a^b の最高位が 1 でないときは 1 を見つけて swap する
    int exchange = n-1;
    int c = a^b;
    if (!(c & (1<<(n-1)))) {
        for (int d = 0; d < n-1; ++d) if (c & (1<<d)) exchange = d;
    }
    swa(a, n-1, exchange), swa(b, n-1, exchange);

    // 前半戦: テキトーに最後尾のビットを入れ替えておく
    int na = a & ~(1<<(n-1));
    auto zenhan = solve(n-1, na, na^1);

    // 後半戦
    int nb = b & ~(1<<(n-1));
    auto kouhan = solve(n-1, na^1, nb);

    // マージする
    vector<int> res;
    if (a & (1<<(n-1))) {
        for (auto v : zenhan) res.push_back(v ^ (1<<(n-1)));
        for (auto v : kouhan) res.push_back(v);
    }
    else {
        for (auto v : zenhan) res.push_back(v);
        for (auto v : kouhan) res.push_back(v ^ (1<<(n-1)));
    }

    // 最後に swap して戻す
    for (auto &v : res) swa(v, n-1, exchange);
    return res;
}

int main() {
    int N, A, B; cin >> N >> A >> B;
    int C = A ^ B;
    int bitcount = 0;
    for (int i = 0; i < N; ++i) if (C & (1<<i)) ++bitcount;
    if (bitcount % 2 == 0) {
        cout << "NO" << endl;
        return 0;
    }
    auto res = solve(N, A, B);
    cout << "YES" << endl;
    for (auto v : res) cout << v << " ";
    cout << endl;
}

順列にもそれに対応する $n$ 次元立体を考えることができます。その立体上での辺の移動は swap に対応しています。↩

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます