【C++】全プレイヤーの合計が等しくなるようにカードを配る方法を見つけるコード

問題概要

n個の要素からなる配列Aがあるとします。ここでnは偶数であり、A[i]はi番目のカードに書かれた数値を表します。ゲームにはn/2人のプレイヤーが参加し、開始時に各プレイヤーは2枚のカードを受け取ります。このとき、どのプレイヤーの手元でも、2枚のカードに書かれた数値の合計が等しくなるようにカードを配分する方法を見つける必要があります。

例えば、入力が A = [1, 5, 7, 4, 4, 3] の場合、出力は [(0, 2), (5, 1), (3, 4)] となります。これは A[0] + A[2] = 8、A[5] + A[1] = 8、A[3] + A[4] = 8 となり、全員の合計が8で一致するためです。

解法のアプローチ

この問題は「貪欲法（グリーディ法）」で解くことができます。ポイントは以下のとおりです。

• 各カードを「値」と「元のインデックス」のペアとして管理する。
• ペアの配列を値の昇順にソートする。
• ソート後、最も小さい値のカードと最も大きい値のカードを順にペアにしていく（i番目と n−i−1 番目を組み合わせる）。

なぜ最小値と最大値を組ませると正しいのか

直感的には「小さい数と大きい数を組み合わせると平均に近づく」ことが分かります。厳密に考えると、等しい合計となる配り方が存在する場合、その合計をSとすると、最小値mのパートナーは必ずS−m、最大値MのパートナーはS−Mになります。ここで x ≤ M、y ≥ m より、S = m + x ≤ m + M ≤ M + y = S が成り立ち、m + M = S であることが示せます。つまり、解が存在する限り、この貪欲なペアリングは必ず正しい答えを導きます。

アルゴリズムの手順

1. 配列Aのサイズをnとする。
2. (値, インデックス) のペアを格納する配列pを用意し、すべての要素を設定する。
3. pを昇順にソートする。
4. i = 0 から n/2 − 1 までループし、p[i].second（インデックス）と p[n − i − 1].second をペアとして出力する。

C++での実装例

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

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

void solve(vector<int> A){
   int n = A.size();
   pair<int, int> p[n];
   for (int i = 0; i < n; i++){
      p[i].first = A[i];
      p[i].second = i;
   }
   sort(p, p + n);
   for (int i = 0; i < n / 2; i++)
      cout << "(" << p[i].second << ", " << p[n - i - 1].second << "), ";
}

int main(){
   vector<int> A = { 1, 5, 7, 4, 4, 3 };
   solve(A);
}

実行結果

入力：

{ 1, 5, 7, 4, 4, 3 }

出力：

(0, 2), (5, 1), (3, 4),

計算量

ソートに O(n log n)、ペアリングのループに O(n/2) かかるため、全体の時間計算量は O(n log n) です。また、ペア配列の分だけ追加の記憶領域として O(n) を使用します。