C++でn組の整数ペアの最小差を求めるプログラムを解説

問題概要

2つの整数配列 a と b が与えられ、それぞれ n 個と m 個の要素を持っているとします。これらの配列から値を取り出し、n 個または m 個のうち小さい方の数だけペアを作成します。各ペアには、必ず配列 a からの値を1つと配列 b からの値を1つ含める必要があります。そして、すべてのペアにおける2つの値の差が「最小かつ同一」になるようにペアを構成し、その差の値を出力します。

たとえば、入力が n = 4、m = 4、a = {2, 3, 4, 7}、b = {3, 4, 6, 5} の場合、出力は 1 になります。

このとき作成できるペアは以下のとおりです。

(3, 4), (4, 5), (7, 6), (2, 3)

すべてのペアの値の差が 1 になっていることが分かります。

解法のステップ

この問題を解くためには、次の手順に従います。

配列 a を昇順にソートする
0 で初期化した配列 s1 を用意する
0 で初期化した配列 s2 を用意する
i := 1 から始めて i < n の間、i を 2 ずつ増やしながら:
   s1 の末尾に「s1 の末尾の要素 + a[i] - a[i-1]」を追加する
i := 2 から始めて i < n の間、i を 2 ずつ増やしながら:
   s2 の末尾に「s2 の末尾の要素 + a[i] - a[i-1]」を追加する
ans := 無限大
配列 b の各値 w について:
   diff := ソート済み配列 a 内で w 以上となる最初の要素のインデックス
   sub := s1[diff / 2] + (s2 の末尾の要素 − s2[diff / 2]) + |a[(diff / 2) × 2] − w|
   ans := ans と sub の小さい方
ans を出力する

アルゴリズムの考え方

配列 a を昇順にソートすると、隣り合う要素同士をペアにするのが最適であることが分かります。s1 は奇数インデックス側の隣接要素間の差の累積和、s2 は偶数インデックス側のそれをそれぞれ保持しています。配列 b の各候補値 w に対しては、二分探索(lower_bound)によって w がソート済み配列 a のどこに挿入されるべきかを求め、その位置に応じたペアリングのコストを累積和を使って効率的に計算します。これにより、全体の計算量は O((n + m) log n) に抑えられます。

C++実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int n, int m, vector<int> a, vector<int> b){
    sort(a.begin(), a.end());
    vector<int> s1 = {0};
    vector<int> s2 = {0};
    for (int i = 1; i < n; i += 2)
        s1.push_back(a[i] - a[i - 1] + s1.back());
    for (int i = 2; i < n; i += 2)
        s2.push_back(a[i] - a[i - 1] + s2.back());
    int ans = INF;
    for (const auto & w : b) {
        int diff = lower_bound(a.begin(), a.end(), w) - a.begin();
        int sub = s1[diff / 2] + s2.back() - s2[diff / 2] + abs(a[diff / 2 * 2] - w);
        ans = min(ans, sub);
    }
    cout << ans << endl;
}

int main() {
    int n = 4, m = 4;
    vector<int> a = {2, 3, 4, 7}, b = {3, 4, 6, 5};
    solve(n, m, a, b);
    return 0;
}

入力

4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}

出力

1