パ研合宿2020 第1日「SpeedRun」 : O - Xor Sum Sum

パッと解法が出なかった。
https://atcoder.jp/contests/pakencamp-2020-day1/tasks/pakencamp_2020_day1_o

問題

N要素の2つの整数列A,Bが与えられる。
0～(N-1)のindexの部分集合S={k[0],k[1]...}を考える。
(A[k[0]]^A[k[1]]^...)+(B[k[0]]^B[k[1]]^...)の最大値を求めよ。

解法

Bを無視しAだけを考えた場合、定番テクでAの各要素をbitvectorとみなし、基底ベクトルを求めるテクが取れる。
この問題ではA・Bの最大値が小さいので、C[i]=A[i]*2^10+B[i]としてCの基底ベクトルを求めてみよう。
この基底ベクトルは高々20個である。
そこで2^20通り基底ベクトルを組み合わせてみて、Aの部分のxorとBの部分のxorがどうなるか総当たりしてみよう。

vector<int> add(vector<int> T,int v) {
	FORR(t,T) v=min(v,t^v);
	if(v) T.push_back(v);
	//sort(ALL(T)); reverse(ALL(T));
	return T;
	
}
int N;
int A[1010101],B[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> V;
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,N) V=add(V,A[i]*1024+B[i]);
	
	int ma=0,mask;
	FOR(mask,1<<V.size()) {
		int a=0;
		FOR(i,V.size()) if(mask&(1<<i)) a^=V[i];
		ma=max(ma,a/1024+a%1024);
	}
	cout<<ma<<endl;
}

まとめ

うーむ。