Codeforces Global Round 3 : F. Foo Fighters

6部は1回読んだけどあまり覚えてないんだよなあ。
https://codeforces.com/contest/1148/problem/F

問題

N個の整数対(V[i], mask[i])が与えられる。
今ここで整数Sを選択しよう。

mask[i]とSのbitwise-andを取ったとき、2進数表記で1の桁が奇数個あった場合、V[i]の符号を反転させるものとする。
適切なSを選択したとき、元のV[i]の総和と、符号反転後のV[i]の総和の符号が反対になるようにせよ。

解法

まず、Vの総和が最初負だったら、全体のV[i]の符号を反転させておこう。
こうするとVの総和は常に正で、適切なSを選択してVの総和を負に持ち込む問題となる。

さて、整数対を、mask[i]のMSBの位置毎に分類しておく。
次に、Sの各ビットの値を下から決めていこう。今、(j-1)ビット目まで決まったものとし、jビット目を決めるものとする。

とりあえずSのjビット目は0としておき、mask[i]のMSBがjビット目であるものに対し、そこまで決まったSを適用した際にV[i]の和が正負どちらになるか見てみよう。
この時、V[i]の総和が正であれば、Sのjビット目を1にすると、この和は負になる。
…という手順を繰り返し、Sの下のビットから決めていこう。

int N;
ll A[303030],B[303030];
vector<int> C[70];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll S=0;
	
	FOR(i,N) {
		cin>>A[i]>>B[i];
		S+=A[i];
		x=0;
		FOR(j,63) if(B[i]&(1LL<<j)) x=j;
		C[x].push_back(i);
	}
	
	if(S<0) {
		FOR(i,N) A[i]=-A[i];
	}
	
	ll mask=0;
	FOR(i,63) {
		ll T=0;
		FORR(c,C[i]) {
			if(__builtin_popcountll(B[c]&mask)%2==1) {
				T-=A[c];
			}
			else {
				T+=A[c];
			}
		}
		
		if(T>0) mask |= 1LL<<i;
	}
	cout<<mask<<endl;
}

まとめ

聞いてしまえばすぐだけど、これ本番に自力で求めるの大変だな。