【C++解説】2つのグループから編成できる3人チームの最大数を求める方法

問題概要

この問題では、2つの整数 N と M が与えられます。N はグループ1の人数、M はグループ2の人数を表します。私たちのタスクは、この2つのグループから編成できる3人チームの最大数を求めるプログラムを作成することです。

チームは3人で構成され、各チームには必ず両方のグループから少なくとも1人ずつが含まれている必要があります。この条件を満たしながら、できるだけ多くのチームを作ることが目標となります。

入出力の例

具体例を使って問題を理解しましょう。

入力: N = 5, M = 3

出力: 2

説明:

チームは以下のように編成されます。

チーム1: グループ1のメンバー → 2人、グループ2のメンバー → 1人
残り: グループ1 = 3人、グループ2 = 2人
チーム2: グループ1のメンバー → 2人、グループ2のメンバー → 1人
残り: グループ1 = 1人、グループ2 = 1人
これ以上3人チームを編成することはできません。

解決アプローチ

この問題を効率的に解くための基本的な戦略は、人数が少ないグループから1人、人数が多いグループから2人を選んでチームを作ることです。この方法により、人数の偏りを抑えながら、両グループのメンバーを含むという条件を満たすチームを最大化できます。

アルゴリズムの手順は以下の通りです。

1. 両グループにそれぞれ1人以上のメンバーが残っており、かつ合計人数が3人以上である間、ループを続けます。
2. 人数が多い方のグループから2人、少ない方のグループから1人を取り出してチームを編成します。
3. 各グループの残り人数を更新し、チーム数を1つ増やします。
4. チーム編成が不可能になった時点で、チームの総数を結果として返します。

C++での実装例

以下は、2つのグループから編成できる3人チームの最大数を求めるC++プログラムです。

#include <iostream>
using namespace std;

int CountTeams(int N, int M) {
    int teamCount = 0;
    while (N >= 1 && M >= 1 && N + M >= 3) {
        if (N > M) {
            N = N - 2;
            M = M - 1;
        } else {
            N = N - 1;
            M = M - 2;
        }
        teamCount++;
    }
    return teamCount;
}

int main() {
    int N = 5, M = 3;
    cout << "3人チームの最大数は " << CountTeams(N, M);
    return 0;
}

実行結果

3人チームの最大数は 2

計算量の分析

このアルゴリズムでは、ループが1回実行されるごとに必ず3人のメンバーが消費されるため、時間計算量は O((N + M) / 3) となります。また、追加のメモリを必要としないため、空間計算量は O(1) で非常に効率的です。

まとめ

2つのグループから3人チームを編成する問題は、貪欲法（Greedy法）を用いることでシンプルに解決できます。人数の少ないグループから1人、多いグループから2人を選ぶ戦略を繰り返し適用することで、常に両グループのメンバーを含むチームの最大数を求められます。条件判定（各グループに1人以上、合計3人以上）をループの継続条件に組み込むことで、無駄のない実装が可能です。