yukicoder : No.2918 Divide Applicants Fairly

割と典型より。
https://yukicoder.me/problems/no/2918

問題

整数列Rが与えられる。
いくつかの要素を数列A、いくつかの要素を数列Bに振り分ける。
どちらの数列にも入れないRの要素があってもよいが、A,Bは空であってはならない。

|A|=|B|で、かつ|sum(A)-sum(B)|の最小値を求めよ。

解法

|A|・|B|が13以上の場合、鳩ノ巣原理から必ずsum(A)=sum(B)となるようにできる。
Nが25以下の場合は、半分全列挙で解く。
Rの前半分について、Aの要素数の超過分に対し、sum(A)-sum(B)の値の一覧を列挙しておこう。
同様に後半分について、Aの要素数の不足分に対し、sum(A)-sum(B)の値の一覧を列挙しておき、前者と二分探索や尺取り法を行い和が0に近いものを探す。

要素数が0のケースを選ばないように注意。

int N;
int R[44];

vector<int> V[2][15];
vector<int> W[2][15];

void dfs(int cur,int vis,int num,int rate) {
	if(cur>=N/2) {
		if(num<0) num=-num,rate=-rate;
		V[vis][num].push_back(rate);
		return;
	}
	dfs(cur+1,1,num+1,rate+R[cur]);
	dfs(cur+1,vis,num,rate);
	dfs(cur+1,1,num-1,rate-R[cur]);
}
void dfs2(int cur,int vis,int num,int rate) {
	if(cur<N/2) {
		if(num<0) num=-num,rate=-rate;
		W[vis][num].push_back(rate);
		return;
	}
	dfs2(cur-1,1,num+1,rate+R[cur]);
	dfs2(cur-1,vis,num,rate);
	dfs2(cur-1,1,num-1,rate-R[cur]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>R[i];
	
	if(N>=26) {
		cout<<0<<endl;
		return;
	}
	
	dfs(0,0,0,0);
	dfs2(N-1,0,0,0);
	int ret=1<<30;
	int a,b;
	FOR(i,15) {
		FOR(a,2) FOR(b,2) if(a+b>0) {
			sort(ALL(V[a][i]));
			sort(ALL(W[b][i]));
			V[a][i].erase(unique(ALL(V[a][i])),V[a][i].end());
			W[b][i].erase(unique(ALL(W[b][i])),W[b][i].end());
			reverse(ALL(W[b][i]));
			if(V[a][i].empty()||W[b][i].empty()) continue;
			x=W[b][i].size()-1;
			FORR(v,V[a][i]) {
				while(x>0&&abs(v-W[b][i][x-1])<abs(v-W[b][i][x])) x--;
				for(j=x-2;j<=x+2;j++) if(j>=0&&j<W[b][i].size()) {
					ret=min(ret,abs(v-W[b][i][j]));
				}
			}
		}
	}
	cout<<ret<<endl;
}

まとめ

Rの上限値が80000と中途半端なの、N≧26をはじくというところから逆算で出したのかな。