kmjp's blog

競技プログラミング参加記です

Codeforces ECR #076: F. Make Them Similar

Fまでは割と簡単な回。
https://codeforces.com/contest/1257/problem/F

問題

非負整数2値が似ているとは、2進数表記で1の数が等しい場合を指す。
ここで数列Aが与えられる。全要素に対し定数xを用いてB[i]=A[i] xor xとして数列Bを作ったとき、Bの要素が互いに等しくなるようなxが存在すればそれを求めよ。

解法

半分全列挙で解く。
Aの各要素は2^30未満なので、xの上15桁を総当たりし、その時の1のビットの数の階差数列を取ろう。
同様にした15桁を総当たりし、前者とプラスマイナスが反転したものがあれば、それを組み合わせるとよい。

int N;
int A[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	map<vector<int>,int> M;
	FOR(x,1<<15) {
		vector<int> C;
		FOR(i,N) {
			y=(A[i]>>15)^x;
			C.push_back(__builtin_popcount(y));
		}
		for(i=N-1;i>=0;i--) C[i]-=C[0];
		M[C]=(x<<15);
	}
	
	FOR(x,1<<15) {
		vector<int> C;
		FOR(i,N) {
			y=(A[i]&((1<<15)-1))^x;
			C.push_back(__builtin_popcount(y));
		}
		for(i=N-1;i>=0;i--) {
			C[i]-=C[0];
			C[i]=-C[i];
		}
		if(M.count(C)) {
			cout<<(M[C]|x)<<endl;
			return;
		}
	}
	cout<<-1<<endl;
	
	
}

まとめ

これは割とすんなり思いついたんだよな。