【C++】3つのソート済み配列から選ぶ三つ組の(max−min)を最小化するアルゴリズム

問題の概要

サイズが必ずしも同じとは限らない、3つのソート済み配列 A、B、C が与えられます。このとき、各配列から1要素ずつ選んでできる三つ組 A[i]、B[j]、C[k] について、その最大値と最小値の差、すなわち max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) を最小化するのが本問題の目的です。

入力例1：

A : [ 2, 5, 6, 9, 11 ]
B : [ 7, 10, 16 ]
C : [ 3, 4, 7, 7 ]

出力：

1

説明：
A[i] = 6、B[j] = 7、C[k] = 7 を選択すると、max − min = |7 − 6| = 1 となり、これが最小の差になります。

入力例2：

A = [ 6, 9, 11, 16 ]
B = [ 7, 10, 16, 79, 90 ]
C = [ 3, 4, 7, 7, 9, 9, 11 ]

出力：

1

説明：
A[i] = 11、B[j] = 10、C[k] = 11 を選択すると、max − min = |11 − 10| = 1 となり、これが最小値となります。

アプローチ（解法の考え方）

この問題は、全ての三つ組を総当たりで調べる必要がなく、効率的に解くことができます。手順は以下の通りです。

まず、各配列 A、B、C の最大要素（末尾の要素）から処理を開始します。そして、現在の三つ組における「最大値 − 最小値」を記録する変数を用意し、ステップごとに答えを更新していきます。

各ステップにおいて、差を小さくする唯一の方法は、3つの要素の中で最大のものを減らすことです。したがって、現時点で最大要素を含む配列を特定し、その配列内で次に大きい要素へと移動して、答えの変数を更新します。

この操作を、最大要素を含む配列の先頭まで到達する（インデックスが尽きる）まで繰り返します。最終的に記録された最小の差が答えとなります。

この手法では、各配列を高々1回ずつ走査するだけなので、時間計算量は O(n + m + k)（n、m、k は各配列の長さ）となり、非常に効率的です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int solve(int A1[], int B1[], int C1[], int i1, int j1, int k1) {
    int min_diff, current_diff, max_term;

    // 各リストの最後のインデックスから最小の差を計算
    min_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
                 - min(A1[i1], min(B1[j1], C1[k1])));

    while (i1 != -1 && j1 != -1 && k1 != -1) {
        current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
                         - min(A1[i1], min(B1[j1], C1[k1])));

        // より小さい差が見つかれば更新
        if (current_diff < min_diff)
            min_diff = current_diff;

        // 現在の三つ組の中で最大の要素を求める
        max_term = max(A1[i1], max(B1[j1], C1[k1]));

        // 最大要素を含む配列のポインタを1つ前に進める
        if (A1[i1] == max_term)
            i1 -= 1;
        else if (B1[j1] == max_term)
            j1 -= 1;
        else
            k1 -= 1;
    }
    return min_diff;
}

int main() {
    int D1[] = { 5, 8, 10, 15 };
    int E1[] = { 6, 9, 15, 78, 89 };
    int F1[] = { 2, 3, 6, 6, 8, 8, 10 };

    int nD = sizeof(D1) / sizeof(D1[0]);
    int nE = sizeof(E1) / sizeof(E1[0]);
    int nF = sizeof(F1) / sizeof(F1[0]);

    cout << solve(D1, E1, F1, nD - 1, nE - 1, nF - 1);

    return 0;
}

出力

1

まとめ

3つのソート済み配列から選ぶ三つ組の最大値と最小値の差を最小化する問題は、最大要素を担う配列のポインタを順次後退させる貪欲的な手法により、線形時間 O(n + m + k) で解くことができます。ソート済み配列という前提条件を活かすことで、総当たり方式（O(n・m・k)）と比べて大幅に計算コストを削減できる点がポイントです。