ABC126 F - XOR Matching (600)

令和ABC初回。残念ながらunratedでした。

F - XOR Matching

概要

整数M, Kが与えられる。長さが2^(M+1)の数列aで下記を満たす数列が構築できる場合、その数列を1つ出力せよ。できない場合-1を出力せよ。

• 要素に0, 0, 1, 1, ... 2^M, 2^Mをもつ
• a[i] = a[j] となる任意のi, j (i < j)について、ai xor a[i+1] xor ... xor a[j] = Kを満たす

制約

0 ≦ M ≦ 17
0 ≦ K ≦ 10^9

方針

0 0 1 1 2 2 …のような作り方をするとK = 0の場合が構築できることは分かったが、それ以外の方針がなかなか思いつかなかった。なので実験してみた。（実験用コード参照）

M = 2 （実験用だとn=4）の時はK = 1, 2, 3どれも作れることが分かった。
規則性を確認していると、下記の点に気づいた。

Fは小さなn全探索するコード書いて観察したら
02313201で1, 01323102で2, 01232103で3が出来たのは見つけた

— misora192 (@misora192) 2019年5月19日

なので、下記の順に出力するとよい。

• 0, 1, ..., 2^M-2, 2^M-1（ただしKは出力しない）
• K
• 2^M-1, 2^M-2, ... , 1, 0 （ただしKは出力しない）
• K

M = 1の時はこのような構築が出来ないため、K=0, 1それぞれ直接解答を出力する。

感想

コンテストは実装途中で終わった。。

解答

Submission #5485177 - AtCoder Beginner Contest 126

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int M, K;
	cin >> M >> K;
 
	if(K >= (1 << M)){
		cout << -1 << endl;
		return 0;
	}
 
	if(M == 1){
		if(K == 0){
			cout << "0 0 1 1" << endl;
		}else{
			cout << -1 << endl;
		}
	}else{
		for(int i = 0; i < (1 << M); i++){
			if(i == K) continue;
			cout << i << " ";
		}
 
		cout << K << " ";
 
		for(int i = (1 << M) - 1; i >= 0; i--){
			if(i == K) continue;
			cout << i << " ";
		}
 
		cout << K << " ";
	}
 
	cout << endl;
}

実験用コード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n = 4;
	vector<int> v(2*n);
	rep(i, 2 * n){
		v[i] = i/2;
	}


	do{
		int a = -1;
		bool ok = true;

		// rep(i, 2*n){
		// 	cout << v[i];
		// }
		// cout << endl;

		vector<bool> chked(n, false);
		for(int i= 0; i < 2*n;i++){
			int c = v[i];
			if(chked[c]) continue;
			chked[c] = true;

			int t = c;
			for(int j = i+1; j < 2*n; j++){
				t ^= v[j];
				if(v[j] == c) break;
			}

			if(a == -1){
				a = t;
			}else{
				if(t != a) {
					ok = false;
					break;
				}
			}
		}

		if(ok){
			if(a == 0) continue;
			rep(i, 2*n){
				cout << v[i];
			}
			cout << "," << a << endl;
		}
	}while(next_permutation(v.begin(), v.end()));

}