kmjp's blog

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

CSAcademy Round #60 : D. Card Groups

えらく手間取った。
https://csacademy.com/contest/round-60/task/card-groups/

問題

N枚のカードがある。
各カードは各面が赤か青で、それぞれ整数が書かれている。
 
各カード赤か青どちらかの面を表に置いた状態にしたとき、各色の整数の和が一致するようにしたい。
そのような置き方の一例を答えよ。
解が複数あるばあい、赤と青のカード枚数の差が少ない方を答えよ。

解法

Nが40以下なので、整数の和に関しては半分全列挙で処理すればよいことは容易に想像できる。
ただ問題はカード枚数の差で、そのため整数和が同じでもカード枚数が異なるケースは別々に覚えておかないといけない。

これをmapを使おうとすると、定数倍高速化や半分全列挙の分割数のバランスをかなり調整しないとTLEする。
半分全列挙の過程で一旦値をvectorにしまい、あとでsortするようにするともう少し余裕を持って間に合う。

int N;
int A[40],B[40];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
	}
	
	vector<pair<ll,int>> V,V2;
	
	for(int mask=0;mask<1<<20;mask++) {
		ll sum=0;
		FOR(i,20) {
			if(mask&(1<<i)) sum+=B[i];
			else sum-=A[i];
		}
		V.push_back({sum,{(__builtin_popcount(mask)<<20) | mask}});
	}
	sort(ALL(V));
	pair<ll,int> p={-1,0};
	swap(V2,V);
	
	FORR(v,V2) {
		if(v.first==p.first && (v.second>>20)==(p.second>>20)) continue;
		p=v;
		V.push_back(p);
	}
	ll cand=-1;
	int best=64;
	for(int mask=0;mask<1<<20;mask++) {
		int on=__builtin_popcount(mask);
		ll sum=0;
		FOR(i,20) {
			if(mask&(1<<i)) sum+=B[i+20];
			else sum-=A[i+20];
		}
		x=lower_bound(ALL(V),make_pair(-sum,0))-V.begin();
		while(x<V.size() && V[x].first==-sum) {
			int dif=abs(N-2*(on+(V[x].second>>20)));
			if(dif<best) {
				cand=(((ll)mask)<<20) | (V[x].second&0xFFFFF);
				best=dif;
			}
			x++;
		}
	}
	
	if(cand!=-1) {
		FOR(i,N) cout<<((cand>>i)&1);
		cout<<endl;
	}
	else {
		cout<<-1<<endl;
	}
}

まとめ

何度も値を突っ込むことがあって、かつ一旦突っ込んだらあとで更新しない場合、mapよりvector+sortの方がいいということをいつも忘れる。