600 点問題ともなると、さすがに正解者数も少ない。
色んな人が色んな構築してそうだけど、僕なりの方法をば。
問題概要
を 以上の整数とする。
以上 以下の整数が 2 個ずつあって、これを並べ替えてできる長さ の数列 であって、
- となるような任意の に対して、 となっている
ようなものを一つ求めよ。存在しない場合は -1 を出力せよ。
制約
考えたこと
こういうのはまずは小さい で作ってみる。
M = 0 のとき、
0 が 2 個しかなくて、作れる数列も "0 0" しかない。K = 0 ならこれを出力して、K > 0 なら -1。
M = 1 のとき、
"0 0 1 1" とかだけど、どう並べても K = 0 にしかできない。
M >= 2 のとき
この辺りから色んな で作れることがわかってくる。まず のときは、例えば だったら
- 0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0
とかで OK。 のときは明らかにダメなので、 の場合を考える。実は必ず作れることがわかる。
例えば、 のとき
- 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 を使う」という風にしている。なんかうまいことできてる。あとは各 に対してこういうペアリングが求められればよくて
- 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); }