【C++】合計が3の倍数になるサイズ2・3のグループの数を効率的に数える方法

はじめに

この記事では、与えられた配列の中から「要素の合計が3の倍数になる」サイズ2または3のグループがいくつ作れるかを求めるC++プログラムを解説します。

問題の概要

整数の配列が与えられたとき、以下の条件を満たすグループの総数を数えます。

• グループのサイズは2つまたは3つの要素
• グループ内の要素の合計が3で割り切れること

例として、配列 {3, 6, 7, 2, 9} を考えます。この場合、条件を満たすグループは8通り存在します。

アルゴリズムのポイント

すべての組み合わせを総当たりで調べると計算コストが大きくなりますが、各要素を3で割った余り(0・1・2)ごとの出現回数を数えれば、組み合わせの数を数式で直接求められます。

合計が3の倍数になるのは、余りの組み合わせが次の場合です。

• サイズ2: (0, 0) または (1, 2)
• サイズ3: (0, 0, 0)、(1, 1, 1)、(2, 2, 2)、(0, 1, 2)

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// サイズ2または3のグループ数を返す関数
int count_groups(int arr[], int n){
   int c[3] = {0}, i;
   int res = 0;
   // 余りごとに要素数をカウント
   for (i=0; i<n; i++)
      c[arr[i]%3]++;
   // サイズ2のグループ
   res += ((c[0]*(c[0]-1))>>1);           // (0, 0)
   res += c[1] * c[2];                    //(1, 2)
   // サイズ3のグループ
   res += (c[0] * (c[0]-1) * (c[0]-2))/6;  //(0, 0, 0)
   res += (c[1] * (c[1]-1) * (c[1]-2))/6;  //(1, 1, 1)
   res += ((c[2]*(c[2]-1)*(c[2]-2))/6);    //(2, 2, 2)
   res += c[0]*c[1]*c[2];                  //(0, 1, 2)
   return res;
}
int main(){
   int arr[] = {3, 6, 7, 2, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Required number of groups are " << count_groups(arr,n) << endl;
   return 0;
}

実行結果

Required number of groups are 8

コードの解説

まず、ループで各要素を3で割った余りをインデックスとして使い、c[0]、c[1]、c[2]にそれぞれの出現回数を記録します。サンプル配列 {3, 6, 7, 2, 9} の場合、余りは順に 0, 0, 1, 2, 0 となるため、c[0]=3、c[1]=1、c[2]=1 となります。

続いて、組み合わせの公式を使って各パターンのグループ数を加算します。

• 同じ余り0から2つ選ぶ組合せ:C(c[0], 2) = c[0]×(c[0]-1)/2
• 余り1と余り2を1つずつ選ぶ:c[1]×c[2]
• 同じ余りから3つ選ぶ組合せ:C(c[i], 3) = c[i]×(c[i]-1)×(c[i]-2)/6
• 余り0・1・2から1つずつ選ぶ:c[0]×c[1]×c[2]

これらを合計すると、サンプルでは 3+1+1+3 = 8 という結果が得られます。

計算量

この手法では、余りの分類にO(n)、その後の集計は定数時間で完了するため、全体の計算量はO(n)です。全組み合わせを調べるO(n³)のアプローチと比べて大幅に高速であり、大規模な配列でも実用的に動作します。

まとめ

剰余ごとの出現回数を利用することで、合計が3の倍数になるサイズ2・3のグループ数を線形時間で効率よく求められます。この考え方は、「合計が特定の数で割り切れるペアやグループを探す」問題全般に応用できる汎用的なテクニックです。