yukicoder : No.545 ママの大事な二人の子供

まぁこれ★３でもしょうがないよね。
https://yukicoder.me/problems/no/545

問題

N個の整数対(A[i],B[i])がある。
各整数対iに対し、A[i]とB[i]のどちらかを選んだ時、前者を選んだ値の総和と後者を選んだ値の総和と考える。
両総和の差の絶対値の最小値を求めよ。

解法

半分全列挙で解く。
前半半分に対し、選び方を総当たりし、両総和の差dの集合Sを求める。
同様に後半半分に対し、選び方を総当たりし、両総和の差d(の集合Tを求める。

前半についてd∈Sとなるような選び方をしていたとする。
その場合後半からは差が-dに近いものを選ぶのが良い。
よってTからlower_bound等で-d周辺の値を二分探索し、得られた値d'(d'は-d周辺の値)に対し|d+d'|の最小値を求めればよい。

int N;
ll 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];
	
	if(i==1) return _P("%lld\n",min(A[0],B[0]));
	
	int L=N/2;
	int R=N-N/2;
	
	set<ll> P;
	for(int mask=0;mask<1<<L;mask++) {
		ll dif=0,sum=0;
		FOR(i,L) {
			if(mask&(1<<i)) {
				dif+=A[i];
			}
			else {
				dif-=B[i];
			}
		}
		P.insert(dif);
	}
	
	ll mi=1LL<<50, ret=0;
	for(int mask=0;mask<1<<R;mask++) {
		ll dif=0;
		FOR(i,R) {
			if(mask&(1<<i)) {
				dif+=A[i+L];
			}
			else {
				dif-=B[i+L];
			}
		}
		
		auto it=P.lower_bound(-dif);
		
		if(it!=P.begin()) {
			auto it2=it;
			it2--;
			mi=min(mi,abs(dif+*it2));
			
		}
		if(it!=P.end()) {
			mi=min(mi,abs(dif+*it));
			auto it3=it;
			it3++;
			if(it3!=P.end()) mi=min(mi,abs(dif+*it3));
			
		}
	}
	
	cout<<mi<<endl;
}

まとめ

半分全列挙は★2.5よりは厳しめだよね。