Codeforces ECR #120 : E. Math Test

嫌なタイトル。
https://codeforces.com/contest/1622/problem/E

問題

N人がこれからM問の問題を解く。
各人どの問題が解けるかは事前に与えられている。

各問の配点は、1～MのPermutationとして自由に設定できるものとする。
各人の得点の想定値をX[i]、得点をR[i]としたとき、驚きはsum(|X[i]-R[i]|)で計算される。
驚きが最大となるような配点を定めよ。

解法

sum(|X[i]-R[i]|)を最大化したいので、各人絶対値を取り外しmax(X[i]-R[i],-(X[i]-R[i]))の和を最大化することとする。
各人X[i]-R[i]を取るか-(X[i]-R[i])を取るか2^N通り総当たりすればよい。

各問に対し、配点の何倍分が驚きに寄与するか計算できるので、寄与が大きい順に高い配点を振ろう。

int T,N,M;
ll X[10];
string S[101010];
int ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) cin>>X[i];
		FOR(i,N) cin>>S[i];
		ll ma=-1;
		int mask=0;
		FOR(mask,1<<N) {
			vector<pair<int,int>> cand;
			FOR(x,M) {
				int mul=0;
				FOR(y,N) if(S[y][x]=='1') {
					if(mask&(1<<y)) {
						mul--;
					}
					else {
						mul++;
					}
				}
				cand.push_back({mul,x});
			}
			ll rs=0;
			FOR(y,N) {
				if(mask&(1<<y)) {
					rs+=X[y];
				}
				else {
					rs-=X[y];
				}
			}
			sort(ALL(cand));
			FOR(x,M) {
				rs+=1LL*(x+1)*cand[x].first;
			}
			if(rs>ma) {
				ma=rs;
				FOR(x,M) ret[cand[x].second]=x+1;
			}
		}
		FOR(x,M) cout<<ret[x]<<" ";
		cout<<endl;
	}
}

まとめ

たまに出る、絶対値の最大化はプラス/マイナス両方試せばいいタイプの問題。