C++でa+b+c=dを満たす最大のdを配列から見つける方法

整数の集合が与えられたとき、d = a + b + c を満たす数 d を見つけ、その値を最大化することが目標です。ここで重要なのは、a、b、c、d のすべてが集合内に存在していなければならないという点です。集合の要素数は最小1個、最大1000個であり、各要素は有限の数であるものとします。

例えば、集合が {2, 3, 5, 7, 12} の場合、12 = 2 + 3 + 7 と表現できるため、最大の d は 12 となります。

解法のアプローチ：ハッシュテーブルを活用する

この問題は、ハッシュテーブル（ハッシュマップ）の手法を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。

1. まず、集合内のすべてのペア (a, b) の和 (a + b) をハッシュテーブルに格納します。キーとしてペアの和を、値として対応する要素のインデックスを保存します。
2. 次に、すべてのペア (c, d) に対して走査を行い、その差 (d − c) がハッシュテーブルに存在するかどうかを検索します。
3. 一致が見つかった場合は、同じ要素が重複して使われていないことを必ず確認します。これは、各インデックスが他のペアのインデックスと重なっていないかをチェックすることで実現できます。
4. 条件を満たす組み合わせの中で、最大の d の値を記録していきます。

ハッシュテーブルによる検索は平均的に定数時間で行えるため、総当たり的な4重ループ（O(n⁴)）に比べて大幅に計算量を抑えられます。全体の計算量は O(n²) となり、要素数が最大1000程度であれば十分高速に動作します。

C++での実装例

#include<iostream>
#include<unordered_map>
#include<climits>
using namespace std;
int findElementsInSet(int arr[], int n) {
   unordered_map<int, pair<int, int> > table;
   for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
         table[arr[i] + arr[j]] = { i, j };
      int d = INT_MIN;
      for (int i = 0; i < n - 1; i++) {
         for (int j = i + 1; j < n; j++) {
            int abs_diff = abs(arr[i] - arr[j]);
            if (table.find(abs_diff) != table.end()) {
               pair<int, int> p = table[abs_diff];
               if (p.first != i && p.first != j && p.second != i && p.second != j) d = max(d, max(arr[i], arr[j]));
            }
         }
      }
   return d;
}
int main() {
   int arr[] = { 2, 3, 5, 7, 12 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int res = findElementsInSet(arr, n);
   if (res == INT_MIN)
      cout << "Cannot find the value of d";
   else
      cout << "Max value of d is " << res;
}

実行結果

Max value of d is 12

コードのポイント

• 前処理フェーズ： 二重ループですべてのペアの和を unordered_map に登録します。キーの重複時には後から登録したペアのインデックスで上書きされます。
• 検索フェーズ： 再びすべてのペアに対して絶対差 abs(arr[i] − arr[j]) を計算し、それがハッシュテーブル上の「あるペアの和」と一致するかを調べます。一致すれば、大きい方の値が a + b + c を満たす d の候補になります。
• 重複チェック： 条件式 p.first != i && p.first != j && p.second != i && p.second != j により、同一の要素が複数の役割で二重に使われていないことを保証しています。
• 該当なしの場合： 条件を満たす d が存在しなければ INT_MIN のまま返されるため、main 関数側で「d の値が見つからない」というメッセージを出力します。