残念ながら私はみんなには含まれませんでした(オープンコンテストも不参加)。
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; }
まとめ
まぁここはすんなり。