これは思いつけて良かった。
https://atcoder.jp/contests/abc249/tasks/abc249_g
問題
N枚のカードがあり、カードiの表裏には整数値A[i],B[i]が書かれている。
いくつかカードを選び、その際選んだカードの表面に書かれた整数値のxorの値がK以下となるようにしたい。
この条件を満たした状態で、裏面に書かれた整数値のxorの値の最大値を求めよ。
解法
最大値を求める問題なので、bitvectorとみなして基底ベクトルを求めて行くことを考える。
A[i]はxorの値に上限があるが、B[i]は最大値を求めたいものの上限はない。
そこで、C[i]=(2^31*A[i])+B[i]という値を考えて、この配列Cの基底ベクトルを求めよう。
あとは基底ベクトルを上位からどん欲に選んでいき、上位31bitのxorがKを超えない範囲で、下位31bitを最大化しよう。
int N; ll K; ll A[1010],B[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; vector<ll> V; int is0=0; FOR(i,N) { cin>>A[i]>>B[i]; ll c=(A[i]<<32)|B[i]; FORR(t,V) c=min(c,t^c); if(c) V.push_back(c); } sort(ALL(V)); reverse(ALL(V)); if(V.empty()) { cout<<0<<endl; return; } if(V.back()>=(K+1)<<32) { cout<<-1<<endl; return; } ll ma=-1; ll a=0,b=0; FORR(v,V) { ll x=v>>32; ll y=v&((1LL<<31)-1); if((a^x)>K) continue; vector<ll> V2; FORR(v2,V) if(v2<v) { ll y2=v2&((1LL<<31)-1); FORR(v3,V2) y2=min(y2,y2^v3); V2.push_back(y2); } ll n=b; FORR(v2,V2) n=max(n,n^v2); ma=max(ma,n); a^=x; b^=y; ma=max(ma,b); } cout<<ma<<endl; }
まとめ
AとBをまとめる部分を思いつけて良かった。