TopCoder SRM 846 : Div1 Medium HockeyAllStars

ちょっともったいないタイムロスしてた。
https://community.topcoder.com/stat?c=problem_statement&pm=18025

問題

N人のプレイヤーがおり、それぞれの強さが与えられる。
プレイヤーを以下の3つに分類したい。

• 1つ目のチームに加える
• 2つ目のチームに加える
• いずれにも加えない

ある分類のスコアを、(両チームのプレイヤーの強さの総和の差の絶対値)*(定数K)+(いずれのチームにも加わらないプレイヤーの強さの総和)とする。スコアの最小値を求めよ。

解法

半分全列挙で解く。
半分ずつに分けたプレイヤー群において、分類の仕方を総当たりし、
X = (1つ目のチームのプレイヤーの強さの総和)-(2つ目の～～～総和)
Y = (いずれのチームにも加わらないプレイヤーの強さの総和)
として(X,Y)のペアを求め、かつX順にソートしていこう。

前半半分のプレイヤーを分類したペア(X,Y)と、後半半分のプレイヤーを分類したペア(X',Y')があったとき、X≧X'ならこれらを合わせたスコアは(X-X')*D+Y+Y'である。
言い換えれば、(X,Y)に対し、X'≦Xとなるペア(X',Y')のうち(-X'*D+Y')が最小となるペアを組み合わせれば最小となる。
よって尺取り法の要領で(X,Y)に対する(-X'*D+Y')の最小値を計算しながら、全スコアの最小値を求めよう。

class HockeyAllStars {
	public:
	long long split(vector <int> S, int K) {
		int N=13;
		while(S.size()<N*2) S.push_back(0);
		vector<pair<ll,ll>> D[2];
		int mask,i,s;
		FOR(s,2) {
			FOR(mask,1<<N) {
				for(int sm=mask;sm>=0;sm--) {
					sm=sm&mask;
					int dif=0;
					int u=0;
					FOR(i,N) {
						if(mask&(1<<i)) {
							if(sm&(1<<i)) dif+=S[i+(s*N)];
							else dif-=S[i+(s*N)];
						}
						else {
							u+=S[i+(s*N)];
						}
					}
					D[s].push_back({dif,u});
				}
			}
			sort(ALL(D[s]));
		}
		ll ret=1LL<<60;
		FOR(s,2) {
			ll mi=1LL<<60;
			for(int L=0,R=0;L<D[0].size();L++) {
				while(R<D[0].size()&&D[1][R].first<=D[0][L].first) {
					mi=min(mi,D[1][R].second-D[1][R].first*K);
					R++;
				}
				ret=min(ret,D[0][L].first*K+D[0][L].second+mi);
			}
			
			
			swap(D[0],D[1]);
		}
		return ret;
		
	}
}

まとめ

半分全列挙系の問題、N=1とかNが奇数の扱いが面倒なので、ダミーデータを入れてNを上限にしちゃうの割と好き。