JOI春合宿 2009-day2 Contest

問題文 : コンテスト

解法 :
まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.

次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位にもなれる.)

まずは, 自分より点数が高いチームがX - 1 個あると仮定し, あとはupper_bound などを使って自分より順位を低くしようと努力する. 努力をしても強いチームがいた場合, 勝ち目が無いのでX 位にはなれない.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int N, C;
int team[3000], snum[3000];

bool ok(int rank, vector<int> solo, vector<int> none)
{
	int p = 1;
	
	for (int i = 0; i < N; i++){
		if (snum[i] == 2 && team[i] > team[C]) p++;
	}
	
	if (p > rank) return (false);
	
	
	while (p != rank){
		if (solo.size() != 0){
			if (none.size() == solo.size()){
				solo.pop_back(); none.pop_back();
			}
			else {
				if (none[none.size() - 1] + none[none.size() - 2] > solo[solo.size() - 1] + none[none.size() - 1]){
					none.pop_back(); none.pop_back();
				}
				else {
					solo.pop_back(); none.pop_back();
				}
			}
		}
		else {
			none.pop_back(); none.pop_back();
		}
		p++;
	}
	
	vector<int>::iterator it;
	while (solo.size() || none.size()){
		if (solo.size() != 0){
			if (none.size() == solo.size()){
				int a = upper_bound(solo.begin(), solo.end(), team[C] - none[none.size() - 1]) - solo.begin() - 1;
				int b = upper_bound(none.begin(), none.end(), team[C] - solo[solo.size() - 1]) - none.begin() - 1;
				//printf("%d %d\n", a, b);
				if (a >= 0){
					none.pop_back(); solo.erase(solo.begin() + a, solo.begin() + a + 1);
				}
				else {
					if (b < 0) return (false);
					solo.pop_back(); none.erase(none.begin() + b, none.begin() + b + 1);
				}
			}
			else {
				int a = upper_bound(solo.begin(), solo.end(), team[C] - none[none.size() - 1]) - solo.begin() - 1;
				int b = upper_bound(none.begin(), none.end(), team[C] - solo[solo.size() - 1]) - none.begin() - 1;
				int c = upper_bound(none.begin(), none.end() - 1, team[C] - none[none.size() - 1]) - none.begin() - 1;
				//printf("%d %d %d\n", a, b, c);
				if (a >= 0){
					none.pop_back(); solo.erase(solo.begin() + a, solo.begin() + a + 1);
				}
				else if (b >= 0){
					solo.pop_back(); none.erase(none.begin() + b, none.begin() + b + 1);
				}
				else {
					if (c < 0) return (false);
					none.pop_back(); none.erase(none.begin() + c, none.begin() + c + 1);
				}
			}
		}
		else {
			int pos = upper_bound(none.begin(), none.end() - 1, team[C] - none[none.size() - 1]) - none.begin() - 1;
			//printf("%d\n", pos);
			if (pos < 0) return (false);
			it = none.begin() + pos;
			none.erase(it, it + 1); none.pop_back();
		}
	}
	
	return (true);
}

int main()
{
	vector<int> none;
	
	scanf("%d %d", &N, &C); --C;
	
	memset(team, 0, sizeof(team));
	memset(snum, 0, sizeof(snum));
	
	for (int i = 0; i < 2 * N; i++){
		int score, idx;
		scanf("%d %d", &score, &idx);
		if (idx){
			team[--idx] += score;
			snum[idx]++;
		}
		else none.push_back(score);
	}
	
	sort(none.begin(), none.end());
	
	while (snum[C] < 2){
		team[C] += none[none.size() - 1];
		snum[C]++;
		none.pop_back();
	}
	
	int zero = 0;
	int rank = 1;
	vector<int> solo;
	for (int i = 0; i < N; i++){
		if (snum[i] == 0) zero++;
		else if (snum[i] == 1 && team[i] > team[C]){
			team[i] += none[none.size() - 1];
			snum[i]++;
			none.pop_back();
			rank++;
		}
		else if (snum[i] == 1) solo.push_back(team[i]);
		else if (snum[i] == 2 && team[i] > team[C]) rank++;
	}
	
	sort(solo.begin(), solo.end());
	int left = rank, right = N;
	while (left != right){
		int center = (left + right) / 2;
		
		if (ok(center, solo, none)) right = center;
		else left = center + 1;
	}
	
	printf("%d\n", left);
	
	return (0);
}