Codeforces #673 Div1 C. XOR Inverse

Div1Cにしては簡単。
https://codeforces.com/contest/1416/problem/C

問題

整数列Aが与えられる。
ここで、非負整数Xを指定し、新たな整数列BをB[i]=A[i] xor Xとして作ることを考える。
Bの転倒数を最小とするXを求めよ。

解法

Xの上のbitから決めていく。
各bit、0と1どちらにしたときの転倒数が小さくなるかを見ていこう。

int N;
int A[303030];
pair<int,int> P[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i]={0,i};
	}
	
	int up=1<<30;
	ll ret=0;
	ll in=0;
	for(j=29;j>=0;j--) {
		ll C[2]={};
		ll I[2]={};
		FOR(i,N) {
			x=P[i].second;
			if(i&&(P[i].first)!=(P[i-1].first)) {
				C[0]=C[1]=0;
			}
			if(A[x]&(1<<j)) {
				I[1]+=C[0];
				C[1]++;
			}
			else {
				I[0]+=C[1];
				C[0]++;
			}
		}
		if(I[0]<=I[1]) {
			in+=I[0];
		}
		else {
			in+=I[1];
			ret+=1<<j;
		}
		up|=1<<j;
		FOR(i,N) P[i]={A[i]&up,i};
		sort(P,P+N);
		
	}
	cout<<in<<" "<<ret<<endl;
	
}

まとめ

1250ptだし、Bで出てもおかしくない問題。