問題
https://codeforces.com/contest/1631/problem/C
問題概要
2の累乗である整数nと0 <= k <= n - 1である整数kが与えられる。
n/2個のペアを以下の条件を満たすように作れ。
- 各ペアには0からn-1までの整数が一つずつ含まれている
- ペア毎にbitwise ANDを取り、それらの数の和がkになるようにせよ
- より形式的には、i番目のペアの2つの数を
,
としたとき、
を満たすようにせよ
- より形式的には、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; }
