C++で解く：合計が指定値以下となる最大サイズ2の最小セット数

問題概要

正の整数からなる配列 arr[] が与えられたとき、次の条件を満たす「セット」の最小数を求める問題です。

• 1つのセットに含められる要素は最大2つまでです。2つの要素は配列内で隣接している必要はありません。
• セット内の要素の合計は、与えられたキー（Key）以下でなければなりません。なお、キーは配列内の最大要素以上であると仮定できます。

例

たとえば、arr[] = {1, 2, 3, 4}、k = 5 が与えられた場合、次の2つのペアを作成できます。

{1, 4} と {2, 3}

このように、4つの要素を合計が5以下になるペア2つに分割できるため、答えは「2」となります。

アルゴリズム

この問題は、貪欲法（グリーディ法）と「両端からの2ポインタ」テクニックを組み合わせることで効率的に解けます。

• まず配列を昇順にソートします。
• ソート済み配列の両端（最小値と最大値）にそれぞれポインタを置きます。
• 2つの要素の合計がキー以下であれば、それらを1つのセットにまとめ、両ポインタを内側へ進めます。
• 合計がキーを超える場合は、大きい方の要素を単独のセットとして扱い、そのポインタだけを内側へ移動します。

この戦略が正しい理由は、最大の要素と組み合わせられるのは最小の要素しかない可能性が高いためです。最大値が最小値とすらペアを組めないなら、その最大値は必ず単独のセットにならざるを得ません。

実装例（C++）

#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
    int i, j;
    sort (arr, arr + n);
    for (i = 0, j = n - 1; i <= j; ++i) {
        if (arr[i] + arr[j] <= key) {
            --j;
        }
    }
    return i;
}
int main() {
    int arr[] = {1, 2, 3, 4};
    int key = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
    return 0;
}

出力

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

Minimum set = 2

計算量

• 時間計算量：ソートに O(n log n)、その後の2ポインタ走査に O(n) かかるため、全体で O(n log n) です。
• 空間計算量：追加の領域は不要なため O(1) です（ソートをインプレースで行う場合）。

このように、2ポインタ法を活用することで、シンプルかつ効率的に最小セット数を求めることができます。