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

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

AtCoder ABC 126 F - XOR Matching (青色, 600 点)

600 点問題ともなると、さすがに正解者数も少ない。
色んな人が色んな構築してそうだけど、僕なりの方法をば。

問題へのリンク

問題概要

 M, K 0 以上の整数とする。
 0 以上  2^{M} 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ  2^{M+1} の数列  a であって、

  •  a_i = a_j となるような任意の  i \lt j に対して、 a_{i}  {\rm xor}  a_{i+1}  {\rm xor}  \dots  {\rm xor}  a_{j} = K となっている

ようなものを一つ求めよ。存在しない場合は -1 を出力せよ。

制約

  •  0 \le M \le 17
  •  0 \le K \le 10^{9}

考えたこと

こういうのはまずは小さい  M で作ってみる。

M = 0 のとき、

0 が 2 個しかなくて、作れる数列も "0 0" しかない。K = 0 ならこれを出力して、K > 0 なら -1。

M = 1 のとき、

"0 0 1 1" とかだけど、どう並べても K = 0 にしかできない。

M >= 2 のとき

この辺りから色んな  K で作れることがわかってくる。まず  K = 0 のときは、例えば  M = 3 だったら

  • 0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0

とかで OK。 K >= 2^{M} のときは明らかにダメなので、 1 \le K \lt 2^{M} の場合を考える。実は必ず作れることがわかる。

例えば、 M = 3, K = 5 のとき

  • 0 xor 5 = 5
  • 1 xor 4 = 5
  • 2 xor 7 = 5
  • 3 xor 6 = 5

となっていることを利用して、

  • 0, 5, 1, 4, 5, 0, 4, 1, 2, 7, 3, 6, 7, 2, 6, 3

とかで作ることができた。つまり「前半は 0 xor 5 と 1 xor 4 を使う」「後半は 2 xor 7 と 3 xor 6 を使う」という風にしている。なんかうまいことできてる。あとは各  K に対してこういうペアリングが求められればよくて

  • 0 xor K = K
  • 1 xor (1 xor K) = K
  • 2 xor (2 xor K) = K
  • ...

を列挙すれば、(被りはあるが) ペアリングをすべて求めることができた。

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

void solve(int M, int K) {
    if (M == 0) {
        if (K != 0) cout << -1 << endl;
        else cout << "0 0" << endl;
        return;
    }
    if (M == 1) {
        if (K != 0) cout << -1 << endl;
        else cout << "0 0 1 1" << endl;
        return;
    }

    if (K >= (1<<M)) {
        cout << -1 << endl;
        return;
    }
    if (K == 0) {
        for (int bit = 0; bit < (1<<M); ++bit) {
            cout << bit << " ";
        }
        for (int bit = (1<<M)-1; bit >= 0; --bit) {
            cout << bit << " ";
        }
        cout << endl;
        return;
    }
                

    using pint = pair<int,int>;
    vector<pint> v;
    for (int bit = 0; bit < (1<<M); ++bit) {
        v.push_back(pint(min(bit, bit^K), max(bit, bit^K)));
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < v.size(); i += 2) {
        cout << v[i].first <<  " " << v[i].second << " "
             << v[i+1].first << " " << v[i+1].second << " "
             << v[i].second << " " << v[i].first << " "
             << v[i+1].second << " " << v[i+1].first << " ";
    }
    cout << endl;
}

int main() {
    int M, K; cin >> M >> K;
    solve(M, K);
}