JOI 二次予選 2023 B - ジョイ四人組 (AOJ 0748) (2Q, 難易度 5)

「最大値と最小値の差」を最小化せよと言われたら、最大値または最小値を固定すると上手くいくことが多い！

• 問題へのリンク

問題概要

サイズが 𝑁 であるような 4 つの数列 𝐴,𝐵,𝐶,𝐷 が与えられる。

これらの数列から 1 個ずつ要素を選んで 𝑎,𝑏,𝑐,𝑑 とする。max⁡(𝑎,𝑏,𝑐,𝑑) −min⁡(𝑎,𝑏,𝑐,𝑑) の値の最小値を求めよ。

制約

• 1 ≤𝑁 ≤75000

考えたこと

愚直に全探索すると、𝑂⁡(𝑁4) の計算量となって間に合わないので高速化しましょう。

高速化したいと考えたとき、よく考えることは「ある変数の値を固定してみる」ということです。たとえば、数列 𝐴 から選ぶ要素 𝑎 を固定する、などが考えられます。しかしこのとき、残りの数列 𝐵,𝐶,𝐷 に対して、𝑎 より大きい数を選べば良いのか、𝑎 より小さい数を選べば良いのかが判然としないのです。（8 通り試す手もある）

このように「最大値と最小値の差」を最小化したいという問題では、上を抑えるのと下を抑えるのと同時に考えないといけなくて困ることが多いですね。

そこで、「最大値」と「最小値」のうち、「最小値」を固定してしまうという解法が思い浮かびます。最小値 𝑚 が決まれば、残りの数は、𝑚 以上の範囲でできる限り小さい数を選ぶことに集中できるのです。

最小値を固定する

さて、4 つの数列から 1 個ずつ選んでできる 4 数の最小値として考えられる値は 4⁢𝑁 通りあります。つまり、

• どの数列から選ぶか（4 通り）
• その数列のどの要素を選ぶか（𝑁 通り）

をかけ合わせて 4⁢𝑁 通りです。

そして、その最小値を 𝑣 としたとき、各数列に対して 𝑣 以上の最小の整数 𝑤 を求めて、𝑤 −𝑣 の値の最大値を求めます。（これは 𝑂⁡(log⁡𝑁) の計算量で求められます）

この値が最小となるような 𝑣 を探索しましょう。

全体として、𝑂⁡(𝑁⁢log⁡𝑁) の計算量で求められます。

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    vector<vector<long long>> A(4, vector<long long>(N));
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < N; j++) cin >> A[i][j];
        A[i].push_back(INF);
        sort(A[i].begin(), A[i].end());
    }

    long long res = INF;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < N; j++) {
            // 最小値が A[i][j] である場合
            long long tmp = 0;
            for (int k = 0; k < 4; k++) {
                long long v = *lower_bound(A[k].begin(), A[k].end(), A[i][j]);
                tmp = max(tmp, v - A[i][j]);
            }
            res = min(res, tmp);
        }
    }
    cout << res << endl;
}