Rockethon 2014 : C3. The Tournament

ちょっと迷ったけど面白い問題。
http://codeforces.com/contest/391/problem/C3

問題

N人の人がいて、それぞれ現状持っている得点と、その人に勝つのに必要な努力値が与えられる。
ここで、新たに自分がトーナメントに参加し、N人とそれぞれ勝負する。
N人それぞれの相手に勝つと１点もらえるがその分努力値が必要である。
逆に負けても自分はペナルティはないが、相手の得点が１点増える。

最後に自分がK位に入るのに必要な最小努力値を答えよ。
なお、自分と同点の人がいる場合、直接対決で勝っているなら自分の順位が上となる。

解法

初期状態でK位の人の得点がP点とする。
この時自分がK位に入る可能性として以下のものがあるので、最小努力値を選ぶ。

• 勝負の結果N人の人は１点増える可能性があるので、P+2点取れば確実に自分はK位に入れる。よって、努力値の低い順にP+2人選んでその努力値の和を取る。
• P+1点取った場合、(P+2)点以上の人がQ人いるとすると、P点またはP+1点の人に(P-Q)人以上負けないようにすれば良い。
• P点取った場合、(P+1)点以上の人がQ人いるとすると、P点またはP-1点の人に(P-Q)人以上負けないようにすれば良い。

int N,K;
pair<int,int> P[200001];
int E[200001];

ll dodo(int target) {
	int lose=0,win=0,oth=0;
	int i;
	vector<ll> V1,V2;
	
	FOR(i,N) {
		if(P[i].first>target) lose++,V1.push_back(P[i].second);
		else if(P[i].first+1<target) win++,V1.push_back(P[i].second);
		else oth++,V2.push_back(P[i].second);
	}
	int mwin=N-K-win;
	
	V1.push_back(0);
	V2.push_back(0);
	sort(V1.begin(),V1.end());
	sort(V2.begin(),V2.end());
	partial_sum(V1.begin(), V1.end(), V1.begin());
	partial_sum(V2.begin(), V2.end(), V2.begin());
	
	ll mi=1LL<<50;
	for(int x=0;x<V1.size();x++) {
		int y = target - x;
		if(y<mwin) y=mwin;
		if(y>=V2.size()) continue;
		mi = min(mi,V1[x]+V2[y]);
	}
	return mi;
}
ll dodo2(int target) {
	int i;
	vector<ll> V;
	FOR(i,N) V.push_back(P[i].second);
	V.push_back(0);
	sort(V.begin(),V.end());
	partial_sum(V.begin(), V.end(), V.begin());
	if(target>=V.size()) return 1LL<<50;
	return V[target];
	
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	K--;
	if(K==N) return _P("0\n");
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	reverse(P,P+N);
	
	ll tot=min(dodo(P[K].first),dodo(P[K].first+1));
	tot=min(tot,dodo2(P[K].first+2));
	if(tot>=1LL<<50) tot=-1;
	cout << tot << endl;
}

まとめ

勝負の結果自分の点が変化するだけでなく、相手の点が増えるってのが斬新。