C++で解く!各人が最大1人とペアを組める場合の組み合わせ数の求め方

問題概要

コーディングコンテストにN人の参加者がいるとします。ここで、1人の参加者が最大1人の相手としかペアを組めないという条件のもとで、考えられるペアの作り方(ペアリング)の総数を求めるのが目的です。

つまり、1つのペアは最大2人で構成され、参加者は誰ともペアを組まずに単独で参加することも許容されます。

漸化式によるアプローチ

この問題は、次のような漸化式(再帰関係)で解くことができます。

• n = 0 または n = 1 のとき:残っている人がいない、または1人だけのため、count = 1(全員が単独という1通りのみ)

• n ≥ 2 のとき:ある1人に注目すると、その人は「単独で残る」か「他の誰かとペアを組む」かのどちらかです。

  • 単独で残る場合:残りの n-1 人について組み合わせを数える → makePairs(p-1)
  • ペアを組む場合:相手の選び方が (p-1) 通りあり、残りの n-2 人について組み合わせを数える → (p-1)*makePairs(p-2)

  したがって、count = makePairs(p-1) + (p-1)*makePairs(p-2) となります。

具体例で理解する

例1:参加者3人の場合

入力: persons = 3

出力: ペアの作り方の総数 ― 4

説明:

3人を a, b, c とすると、ペアの作り方は以下の通りです。
(a,b), (c) → c が単独
(a,c), (b) → b が単独
(b,c), (a) → a が単独
(a),(b),(c) → 全員が単独
合計 4通り

例2:参加者2人の場合

入力: persons = 2

出力: ペアの作り方の総数 ― 2

説明:

2人を a, b とすると、ペアの作り方は以下の通りです。
(a,b) → 2人でペアを組む
(a),(b) → 両者とも単独
合計 2通り

プログラムのアプローチ

• 参加者の人数を整数 person として受け取ります。

• 関数 makePairs(int p) は人数を引数に取り、ペアの組み合わせ数を返します。

• 初期値として count を 0 に設定します。

• p = 0 または p = 1 の場合は、全員が単独である1通りしかないため count = 1 となります。

• それ以外の場合は、「ある1人が単独で残るケース」と「(p-1) 通りの相手を選んでペアを組むケース」を足し合わせます。

• 最終的な count の値が、ペアの作り方の総数として返されます。

C++コード例

#include<iostream>
using namespace std;
int makePairs(int p){
    int count=0;
    // 基底条件
    if (p==0 || p==1)
       { count=1; }
    else
       { count=makePairs(p-1) + (p-1)*makePairs(p-2); }
    return count;
}
int main(){
    int persons = 5;
    cout <<"Number of ways to make pair ( or remain single ):"<<makePairs(persons);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Number of ways to make pair ( or remain single ): 26

計算量と改善のポイント

この再帰的な実装は非常にシンプルですが、同じ計算を何度も繰り返すため、人数が増えると計算時間が指数的に増大します。実際の開発では、結果を配列やマップにキャッシュするメモ化(動的計画法)を導入することで、計算量を O(n) まで抑えることができます。フィボナッチ数列と似た構造を持つ問題なので、DPへの書き換えも容易です。