C++で3人チームの最大結成数をカウントする方法【アルゴリズムと実装例】

問題概要

n 個の要素を持つ配列 A があるとします。これは n 個の学生グループを表しています。各グループは次のいずれかのタイプです。

• 誰とでもチームを組むことができる 1 人の学生
• 必ず同じチームでコードを書きたい 2 人の学生

しかし、メンターはちょうど 3 人ずつのチームを結成することにしました。ここで求めたいのは、メンターが結成できる 3 人チームの最大数です。なお、2 人グループについては「2 人そろって参加する」か「2 人そろって不参加」のどちらかしか選べず、参加する場合は必ず同じチームに所属しなければなりません。

たとえば、入力が A = [2, 2, 2, 1, 1, 1, 1] の場合、出力は 3 になります。メンターは次のようなチーム編成が可能だからです。

• [1 番目の 2 人グループ + 7 番目の 1 人グループ]
• [2 番目の 2 人グループ + 6 番目の 1 人グループ]
• [3 番目の 2 人グループ + 4 番目の 1 人グループ]

解き方の手順

この問題は、次の手順で効率的に解くことができます。

1. 配列を走査し、1 人グループの総数を p、2 人グループの総数を q としてカウントします。
2. p > q の場合: すべての 2 人グループ(q 個)に 1 人ずつ加えて q チームを作り、余った 1 人グループ(p − q 人)だけでさらに (p − q) / 3 チームを編成できます。したがって答えは q + (p - q) / 3 となります。
3. p ≤ q の場合: 各 1 人グループを異なる 2 人グループに振り分けるのが最適であり、これ以上チームを増やせないため、答えは p となります。

この擬似コードで処理の流れを確認してみましょう。

p := 0
q := 0
x := 配列Aのサイズ
i := 0 から x 未満の間、1 ずつ増やしながら繰り返す:
    a := A[i]
    もし a が 1 と等しいならば:
        p := p + 1
    そうでなければ:
        q := q + 1
もし p > q ならば:
    return q + (p - q) / 3
そうでなければ(p <= q のとき):
    return p

C++ での実装例

理解を深めるために、実際の C++ コードを見てみましょう。計算量は O(n) と非常に効率的です。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
   int p = 0, q = 0;
   int x = A.size();
   for (int i = 0; i < x; i++){
      int a = A[i];
      if (a == 1){
         p = p + 1;
      }
      else{
         q = q + 1;
      }
   }
   if (p > q){
      return q + (p - q) / 3;
   }
   else if (p < q){
      return p;
   }
   else{
      return p;
   }
}
int main(){
   vector<int> A = { 2, 2, 2, 1, 1, 1, 1 };
   cout << solve(A) << endl;
}

入力

{ 2, 2, 2, 1, 1, 1, 1 }

出力

3