C. And Matching (Codeforces Round #768 Div. 2)

問題

https://codeforces.com/contest/1631/problem/C

問題概要

2の累乗である整数nと0 <= k <= n - 1である整数kが与えられる。

n/2個のペアを以下の条件を満たすように作れ。

• 各ペアには0からn-1までの整数が一つずつ含まれている
• ペア毎にbitwise ANDを取り、それらの数の和がkになるようにせよ
  • より形式的には、i番目のペアの2つの数を, としたとき、を満たすようにせよ

考察

問題の制約より、0以上n-1以下の数についてのみ考えます。

また、nは2の累乗なのでn-1はすべてのビットが立っている数です。n=8ならですし、n=16ならです。

k = 0のとき

x AND (x XOR (n - 1))は0となります。x=0のとき(x XOR (n - 1))=n-1、x=1のとき(x XOR (n - 1))=n-2、...、x=n/2-1のとき(x XOR (n - 1))=n/2となるので、0とn-1、1とn-2、2とn-3...、というペアを作っていけばすべて0になり、和ももちろん0になります。

k < n - 1のとき

n-1 XOR x = xが成り立ちます。

また、前述のk = 0のときの解法では、n-1は0とペアになっておりkは(k XOR (n - 1))とペアになっています。ここでn-1とkをペアにして0と(k XOR (n - 1))をペアにすれば、前者でkが作れ後者で0が作れて、その他のペアは変わらず0のままなので最終的な和はkとなります。

k = n - 1のとき

n=4のときは、サンプルにあるとおり構築不可能です。以下n>=8のときで考えます。

上記の解法ではn-1を一発で作ることはできません、n-1とn-1をペアにしないとn-1は作れませんが、n-1はもちろん一度しか使えないためです。

そこで、一旦n-1とn-2をペアにします。これでn-2が作れて、あとは1を作ればよいとなります。とりあえず1 AND 3 = 1なので、それで考えてみます。

この時点で使っていない数は0, 2と4, 5, 6, ..., n-3です。これらについて、k = 0のときの解法と同じロジックで0を作れるペアをすべて作ると0とn-4が残ります。0が残っているのでn-4がいくつであるかにかかわらずペアにすると0です。よってk=n-1も達成できました。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (n == 4 and k == 3) {
            cout << -1 << endl;
            continue;
        } else if (n - 1 == k) {
            cout << 0 << " " << (n - 4) << endl;
            cout << 1 << " " << 3 << endl;
            cout << (n - 2) << " " << (n - 1) << endl;
            for (int i = 0; i < n / 2; i++) {
                if (i == 0 or i == 1 or i == 3) continue;
                cout << i << " " << (i ^ (n - 1)) << endl;
            }
        } else {
            cout << k << " " << n - 1 << endl;
            for (int i = 1; i < n / 2; i++) {
                int r = i ^ (n - 1);
                if (i == k) {
                    cout << 0 << " " << r << endl;
                } else if (r == k) {
                    cout << 0 << " " << i << endl;
                } else {
                    cout << i << " " << r << endl;
                }
            }
        }
    }
    return 0;
}