合計がどちらの配列にも存在しない2つの数値を見つけるC++プログラム

問題概要

n個の要素を持つ配列Aと、m個の要素を持つ配列Bが与えられたとします。ここで、Aからある要素aを、Bからある要素bをそれぞれ選び、その合計 a + b が配列AにもBにも存在しないようにする必要があります。

例えば、入力が A = [3, 2, 2]、B = [1, 5, 7, 7, 9] の場合、出力は [3, 9] となります。これは 3 + 9 = 12 がどちらの配列にも存在しないためです（他にも有効な答えは存在します）。

解法のアプローチ

この問題は、非常にシンプルな発想で効率的に解くことができます。ポイントは「各配列の最大値同士を組み合わせる」ことです。すべての要素が正の整数であれば、最大値同士の合計は必ず両方の配列内のどの要素よりも大きくなるため、その合計が配列に含まれることはありません。

具体的には、以下の手順に従います。

配列Aをソートする
配列Bをソートする
Aの最後の要素とBの最後の要素を出力する

C++での実装例

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

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

void solve(vector<int> A, vector<int> B) {
   sort(A.begin(), A.end());
   sort(B.begin(), B.end());
   cout << A[A.size() - 1] << ", " << B[B.size() - 1];
}
int main() {
   vector<int> A = { 3, 2, 2 };
   vector<int> B = { 1, 5, 7, 7, 9 };
   solve(A, B);
}

入力

{ 3, 2, 2 }, { 1, 5, 7, 7, 9 }

出力

3, 9

このアルゴリズムが機能する理由

各配列の最大値をそれぞれa、bとすると、a + b は必ず a および b よりも大きな値になります（要素がすべて正の整数の場合）。したがって、a + b が配列AやBに含まれることはあり得ません。

計算量についても優れており、ソートに O(n log n + m log m)、最大値の取得は O(1) で完了します。全ペアを総当たりで調べる O(n × m) の方法と比べても、はるかに効率的な解法と言えるでしょう。