JOI春合宿2009 Contest

Contest はやっぱり結構難しいと思う…

解法

hogloid がO(N log N) で解いたらしいが知らない。
下のコードは O(N^2)。
まず、各チームを「2人とも点数分かってる」「1人しか分かってない」「2人とも分かってない」という基準で、A群、B群、C群に分類する。
問われているチームがA群に含まれていた場合は、点数が分かる。B群に含まれていた場合は、C群から最高点を持ってくる。どっちにも含まれない場合は、C群から最高点を2つ持ってくる。
これで基準点が決定したので、できるだけ基準点以下のチームをたくさん作ることを考える。まず、B群の中で基準点を上回っているチームが i あると仮定する。この i 個のチームについては、C群の上位とそれぞれくっつけてしまって構わない。ここで実際には基準点を上回っていなくても無視する。B群の他のチームについては、B群の下位のチームから順に、C群の中の可能な限り上位のチームとつなげる。このとき基準点を超えないようにする。どうしても基準点を超える場合は以後の探索をやめ、次の i に移行する。
そして、C群の残ったチームについては、下位から順に、基準点を超えない限りできるだけ上位とくっつけるということを繰り返す。それでも残ったチームは、適当にくっつける（基準点を超える）。これで、各 i についての最良値が決定する。

コード

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int N, C;
vector<int> As, Bs, Cs; //As: 完全決定 Bs: 片方決定 Cs: 未決定
bool used[6000];
int tm[3000][2];

int main()
{
	int s, a;
	scanf("%d%d", &N, &C); --C;
	for(int i=0;i<N;i++) tm[i][0] = tm[i][1] = -1;

	for(int i=0;i<2*N;i++){
		scanf("%d%d", &a, &s);
		if(s==0) Cs.push_back(a);
		else{
			--s;
			if(tm[s][0]!=-1) tm[s][1] = a;
			else tm[s][0] = a;
		}
	}

	sort(Cs.begin(), Cs.end());
	int ptC = -1;
	for(int i=0;i<N;i++){
		if(tm[i][1] != -1){
			if(i==C) ptC = tm[i][0] + tm[i][1];
			else As.push_back(tm[i][0] + tm[i][1]);
		}else if(tm[i][0] != -1){
			if(i==C){
				ptC = tm[i][0] + Cs[Cs.size() - 1];
				Cs.pop_back();
			}else{
				Bs.push_back(tm[i][0]);
			}
		}
	}
	if(ptC==-1){
		ptC = Cs[Cs.size() - 1] + Cs[Cs.size() - 2];
		Cs.pop_back(); Cs.pop_back();
	}

	sort(Bs.begin(), Bs.end());

	int bas=0, ret=N+1;
	for(int i=0;i<As.size();i++) if(As[i] > ptC) bas++;

	for(int i=0;i<=Bs.size();i++){
		int Cmx = Cs.size() - i;
		for(int j=0;j<Cmx;j++) used[j] = false;
		int rp=Cmx-1;
		int left=0, right=Cmx-1, save=0;
		for(int j=0;j<Bs.size()-i;j++){
			while(rp>=0 && Bs[j] + Cs[rp]>ptC) --rp;
			if(rp<0) goto nex;
			used[rp--] = true;
		}
		while(left<right){
			while(left<right && used[left]) ++left;
			while(left<right && (used[right] || Cs[left]+Cs[right] > ptC)) --right;
			if(left>=right) break;
			save++;
			left++;
			right--;
		}
		ret = min(ret, 1 + i + (int)(Cs.size() - Bs.size()) / 2 - save);
nex:
		continue;
	}
	printf("%d\n", ret + bas);

	return 0;
}