C++でN個の数値から作るN/2ペアの平方和を最小化するアルゴリズム

問題概要

n個の要素を持つ配列が与えられたとき、その要素を使ってn/2個のペアを作成し、各ペアの合計値を2乗したものの総和（平方和）が最小になるようにするのが課題です。

例

次の配列が与えられたとします。

arr[] = {5, 10, 7, 4}

この場合、(4, 10) と (5, 7) のようにペアを作ると、平方和は最小値の 340 になります。

計算内容は以下の通りです。

• (4 + 10)² = 14² = 196
• (5 + 7)² = 12² = 144
• 196 + 144 = 340

アルゴリズム

最小の平方和を求めるための手順は以下の通りです。

1. 配列を昇順にソートする
2. 配列の先頭と末尾を指す2つの変数（start と end）を用意する
3. 次のように合計を計算する：
       sum = arr[start] + arr[end];
       sum = sum * sum;
4. start < end である限りこの手順を繰り返し、minSum に加算していく

While (start < end) {
    sum = arr[start] + arr[end];
    sum = sum * sum;
    minSum += sum;
    ++start;
    --end;
}

なぜこの方法が有効か

数直線上で考えると、大きな数同士や小さな数同士をペアにすると合計値が大きくなり、その2乗はさらに大きく膨らみます。一方、ソート後に「最小値＋最大値」の組み合わせでペアを作ると、各ペアの合計値が平均的に近づき、2乗和を最小化できます。これは数学的にも証明されている有名なテクニックです。

C++での実装例

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinSquareSum(int *arr, int n) {
   sort(arr, arr + n);
   int minSum = 0;
   int start = 0;
   int end = n - 1;
   while (start < end) {
      int sum = arr[start] + arr[end];
      sum *= sum;
      minSum += sum;
      ++start;
      --end;
   }
   return minSum;
}
int main() {
   int arr[] = {5, 10, 7, 4};
   int res = getMinSquareSum(arr, SIZE(arr));
   cout << "Minimum square sum: " << res << "\n";
   return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Minimum square sum: 340

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。ペアを作成するループ部分自体は O(n/2)、つまり O(n) で済みます。また、追加のメモリ領域をほとんど必要としないため、空間計算量は O(1) と非常に効率的です。