kmjp's blog

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

AtCoder ABC #141 : F - Xor Sum 3

今回不参加だったけど、参加してたらちょっと手間取ってそう。
https://atcoder.jp/contests/abc141/tasks/abc141_f

問題

N個の整数値Aが与えられる。これらを2つの集合に分ける。
それぞれの集合内でXORを取った値の総和の最大値を求めよ。

解法

各要素2進数表記し、各桁でビットが立っている箇所の数を数えよう。
もし奇数個の場合、どんな集合の分け方でも、XORを取った結果は片方のビットが立つので、分け方の影響はない。
よってこれらのビットは(解として総和を取ったうえで)Aから取り除こう。

残りをどう分けるかを考える。
Aのうち一部を片方の集合として選択し、そのxorを最大化することを考えよう。
各桁の立っているビットは偶数なので、結果的にもう片方の集合のxorを取った値も同じになるので、とにかく片方の集合を最大化するのが最適である。

これについて、すでに過去Codeforcesで部分問題として登場している。
Aをbitvectorの集合として基底ベクトルを求め、(xorでの)総和が最大になる限り規定ベクトルを取り込んでいくとよい。
Codeforces #532 Div2 F. Ivan and Burgers - kmjp's blog

int N;
ll A[101010];
ll X;

template<class C> vector<C> gf2_rank(vector<C>& V) { /* input */
	int i,j;
	int N=V.size();
	FOR(i,N) {
		int x=max_element(V.begin()+i,V.end())-V.begin();
		if(V[x]==0) break;
		swap(V[i],V[x]);
		C msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		FOR(j,N) if(j!=i) if(V[j]&msb) V[j]^=V[i];
	}
	while(V.size() && V.back()==0) V.pop_back();
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> V;
	FOR(i,N) {
		cin>>A[i];
		X^=A[i];
	}
	FOR(i,N) {
		A[i]&=~X;
		V.push_back(A[i]);
	}
	auto W=gf2_rank(V);
	ll ret=0;
	FORR(v,V) ret=max(ret,ret^v);
	cout<<ret*2+X<<endl;
	
	
	
}

まとめ

令和に入って初めてABC不参加でした。