C++で2種類のアイテムを含むサイズ3のグループの最大数を求める方法

問題の概要

AタイプのアイテムがN個、BタイプのアイテムがM個与えられたとき、サイズ3のグループを最大でいくつ作れるかを求めるのがこの記事の課題です。

ただし、各グループにはAとB両方のタイプのアイテムが、それぞれ少なくとも1個ずつ含まれている必要があります。

具体例で理解しよう

入力: N=3、M=5

出力: 2

説明:

グループ1：Aタイプ1個＋Bタイプ2個
グループ2：Aタイプ1個＋Bタイプ2個
合計でAタイプ2個、Bタイプ4個を使用。

入力: N=5、M=9

出力: 4

解法のアプローチ

この問題は、NとMの大小関係および合計値をもとに、次の4つのケースに分けて考えることができます。

• ケース1：N ≥ 2M の場合
  Aタイプのアイテムが十分に多い状態です。このとき、作成可能な最大グループ数は N となります。

• ケース2：M ≥ 2N の場合
  Bタイプのアイテムが十分に多い状態です。このとき、作成可能な最大グループ数は M となります。

• ケース3：(M+N) % 3 == 0 の場合
  全アイテム数が3で割り切れるため、すべてのアイテムをグループに振り分けられます。最大グループ数は (M+N)/3 となります。

• ケース4：上記のいずれにも該当しない場合
  基本となるグループ数は (M+N)/3 ですが、端数のアイテムだけでもう1グループ追加できるかどうかを確認する必要があります。
  N = N % 3、M = M % 3 として両タイプの残りを求め、次の条件を判定します。

  N != 0 かつ M != 0 かつ (N+M) ≥ 3

  この条件が成立すれば、最終結果に1を加算します。

アルゴリズムの流れ

1. MaxGrp() 関数内で、if文による条件分岐を使って上記の各ケースを順番に判定していきます。
2. まず「N >= 2*M」が真であれば N を答えとして返します。偽の場合は「M >= 2*N」を判定し、真であれば M を返します。
3. どちらの条件も満たさない場合は、「(M+N) % 3 == 0」かどうかを確認し、真であれば (M+N)/3 を返します。
4. いずれの条件にも当てはまらない場合は、int型変数 count を (M+N)/3 で初期化します。続いて N = N % 3、M = M % 3 として残りのアイテムを求め、ケース4の条件を満たしていれば count に1を加算して返します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// 上記の手順を実装した関数
int MaxGrp(int N, int M){
    if (N >= 2 * M)
        return N;
    if (M >= 2 * N)
        return M;
    if ((M + N) % 3 == 0)
        return (M + N)/3;
    int count = (M + N)/3;
    M %= 3;
    N %= 3;
    if (M && N && (M + N) >= 3)
        count++;
    return count;
}
int main(){
    int N = 5, M = 9;
    cout << MaxGrp(N, M);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

4

N=5、M=9 の入力に対して、プログラムは正しく最大グループ数「4」を出力しています。

まとめ

本記事では、2種類のアイテムからサイズ3のグループを最大限に作る問題を、数量関係に基づく4つのケース分岐で解く方法を紹介しました。使用しているのは比較と剰余演算のみのため、計算量はO(1)と非常に効率的で、大きな入力値でも即座に答えを求められるシンプルなアルゴリズムです。