今回不参加だったけど、参加してたらちょっと手間取ってそう。
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不参加でした。