みんなのプロコン (2017) 本選 B - チーム決め
問題概要
N要素の数列AとM要素の数列Bが与えられる。数列からK個の要素を選んで任意の順序で並べる、という操作を両方の数列に対して行ってできる数列をX, Yとする。好きな選び方ができるとき、max(|X_1-Y_1|, ..., |X_K - Y_K|)の最小値を求めよ。
N, M <= 105
解法
2分探索をする。O(NlogN)
ある値αについて差がα以下であるペアをK個以上作れるかどうかを判定していくことで、αの最小値を2分探索できる。ペアをK個以上作れるかどうかは、AとBをあらかじめソートしておいたうえで前から貪欲に決めていくことで判定できる。具体的にはAとBを前から見ていき、もし見ているペアの差がα以下であればペア成立とし、AもBも次の要素に移る。逆に差がαより大きい場合、小さい方だけ次の要素に移る。最終的に作ったペアの数がK以上であればそのαは適格である。
感想
Aの方がむずない?
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto K = s[2]; auto A = readln.split.map!(to!long).array; auto B = readln.split.map!(to!long).array; A.sort(); B.sort(); long hi = 10^^9; long lo = -1; while (hi - lo > 1) { long mid = (hi + lo) / 2; int cnt = 0, i = 0, j = 0; while (i < N && j < M) { if (abs(A[i] - B[j]) <= mid) { cnt += 1; i += 1; j += 1; } else if (A[i] - B[j] > mid) { j += 1; } else { i += 1; } } if (cnt >= K) { hi = mid; } else { lo = mid; } } hi.writeln; }