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; }
まとめ
これは割とすんなり思いついたんだよな。