kmjp's blog

競技プログラミング参加記です

みんなのプロコン本選 : B - チーム決め

残念ながら私はみんなには含まれませんでした(オープンコンテストも不参加)。
http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_b

問題

2つのチームがあり、それぞれのメンバーの実力はA[i],B[i]である。
両チームからK人の人を選び、試合をすることを考える。
試合では、両チームで実力の高い順に1対1で戦う。
その際、対戦相手同士の実力差の絶対値の最大値を最小化せよ。

解法

二分探索+尺取り法で解く。
実力差の絶対値を仮決めしたとき、K組の対戦組み合わせを作れるか判定しよう。

まず両チームのメンバーをまとめて実力昇順に並べ、順に処理していく。
その際、自身の実力との差がK以下の(対戦相手未確定の)相手チームのメンバーがいたら、うち最小の実力の相手を選び、対戦相手成立、とみなす。
尺取り法の要領で未割当のメンバーのうち差がK以下で最小実力値の相手を選んでいくとよい。

int N,M,K;
vector<pair<int,int>> V;
int A[101010],B[101010];

int ok(int d) {
	deque<int> Q[2];
	int match=0;
	int i;
	FORR(r,V) {
		int id=r.second;
		int cur=r.first;
		FOR(i,2) while(Q[i].size() && Q[i].front() < cur-d) Q[i].pop_front();
		if(Q[id^1].size()) {
			match++;
			Q[id^1].pop_front();
		}
		else {
			Q[id].push_back(cur);
		}
		
		
	}
	return match>=K;
	
}

まとめ

まぁここはすんなり。