kmjp's blog

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

AtCoder ABC #249 (モノグサプログラミングコンテスト2022) : G - Xor Cards

これは思いつけて良かった。
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をまとめる部分を思いつけて良かった。