【C++】N人をMチームに分けたときの友人ペア数の最小値と最大値を求める方法

問題概要

競技会に参加した N 人の参加者が、何らかの方法で M 個のチームに分けられました。ただし、各チームには必ず1人以上の参加者が所属するものとします。大会終了後、同じチームに所属していた参加者のペアはそれぞれ「友人」になります。

このとき、大会終了までに形成され得る友人ペアの総数の最小値と最大値を求めるプログラムを作成するのが本記事の課題です。

アルゴリズム（考え方）

ペア数が最大になるケース

ペア数を最大化したいなら、できるだけ多くの人を1つのチームに集中させるのが最適です。具体的には、1つのチームに (n − m + 1) 人を入れ、残りの (m − 1) チームには各1人ずつ配分します。このとき、人数の多いチーム内部で作られる組み合わせの数が全体の最大値となります。

maxPairs = ((n − m) × (n − m + 1)) / 2

ペア数が最小になるケース

逆にペア数を最小化したい場合は、全メンバーをできるだけ均等に各チームへ振り分けます。チーム間の人数の偏りが小さいほど、同一チーム内で成立するペアの総数は減少します。

minPairs = m × (((n − m) / m + 1) × ((n − m) / m)) / 2
         + ceil((n − m) / double(m)) × ((n − m) % m)

ここでは整数除算 (n − m) / m で商を、(n − m) % m で余りを求め、余りが生じた分のペア数を実数除算＋ceil（切り上げ）で補正しています。

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;

void getPairs(int n, int m){
    // 最大ペア数：1チームに人数を集中させる
    int maxPairs = ((n - m + 1) * (n - m)) / 2;

    // 最小ペア数：全員をできるだけ均等に振り分ける
    int minPairs = m * (((n - m) / m + 1) * ((n - m) / m)) / 2
                 + ceil((n - m) / double(m)) * ((n - m) % m);

    cout << "Minimum pairs = " << minPairs << "\n";
    cout << "Maximum pairs = " << maxPairs << "\n";
}

int main(){
    getPairs(3, 2);
    return 0;
}

実行結果

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

Minimum pairs = 1
Maximum pairs = 1

n = 3人を m = 2チームに分ける場合、分け方は「2人と1人」しかありません。このとき同じチーム内で成立するペアはちょうど1組となるため、最小値と最大値が一致します。

別の計算例で確認

もう少し規模の大きい例として、n = 6人、m = 3チームの場合を考えてみましょう。

• 最大値： 4人・1人・1人に分けると、4人のチーム内のペアは 4×3÷2 = 6組。式でも ((6−3)×(6−3+1))÷2 = 6 となり一致します。
• 最小値： 2人・2人・2人に均等に分けると、各チーム1組ずつで合計3組。式でも 3×(1+1)×1÷2 = 3 となり一致します。

このように、「集中させるか、分散させるか」という戦略の違いがそのまま答えの差として現れるのが本問題のポイントです。