みんなのプロコン (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;
}