【C++】R・G・Bだけで構成される文字列の組み合わせ総数を求める方法

3つの整数 R、G、B が与えられ、使用できる文字は「R」「G」「B」の3種類のみとします。この問題の目的は、「R」が少なくともR個、「G」が少なくともG個、「B」が少なくともB個含まれる文字列として作成可能なパターンの総数を求めることです。なお、R＋G＋B の合計は文字列の長さ以下であるものとします。

入力例と出力例

例1

入力：

R = 1, G = 1, B = 1, length = 3

出力：

6

説明：
可能な文字列は以下の6通りです。これは RGB の全順列に相当します。

"RGB", "RBG", "BRG", "BGR", "GRB", "GBR"

例2

入力：

R = 2, G = 0, B = 2, length = 4

出力：

6

説明：
可能な文字列は以下の6通りです。

"RRBB", "BBRR", "RBRB", "BRBR", "RBBR", "BRRB"

解法のアプローチ

この解法では、まず必須となる「R」「G」「B」の文字をそれぞれ規定回数ぶん確保したうえで、残りの長さ size − (R＋G＋B) 分の文字を R・G・B へどう割り振るかをすべて列挙し、各割り振りごとの順列の数（多項係数）を計算してカウントに加算していきます。

• 整数値 R、G、B を入力として受け取ります。
• size には作成する文字列の長さを指定します。
• 関数 combination(int R, int G, int B, int size) がすべての入力を受け取り、条件を満たす文字列の総数を返します。
• カウント用変数 count を 0 で初期化します。
• 残りの文字数を temp = size − (R ＋ G ＋ B) とします。
• 階乗の値を格納するため、サイズ size＋1 の配列 arr を用意します。
• forループ（i = 0 ～ size）により arr[i] に i の階乗を格納します。具体的には arr[i] = arr[i−1] × i と計算します。
• 続いて二重のforループで残り文字の割り振りパターンを列挙します。
• i = 0 ～ temp、j = 0 ～ temp − i の範囲でループし、temp_2 = temp − (i ＋ j) を計算します。
• temp_3 = arr[i ＋ R] × arr[j ＋ B] × arr[temp_2 ＋ G] を求めます。これは各文字の重複度を考慮した分母になります。
• count に arr[size] / temp_3（多項係数）を加算します。
• すべてのループが完了した時点で、count が条件を満たす文字列の総数となります。
• count を結果として返します。

C++実装例

#include<bits/stdc++.h>
using namespace std;
int combination(int R, int G, int B, int size){
    int count = 0;
    int temp = size - (R + G + B);
    int arr[size+1];
    arr[0] = 1;
    for (int i = 1; i <= size; i++){
        arr[i] = arr[i - 1] * i;
    }
    for (int i = 0; i <= temp; i++){
        for (int j = 0; j <= temp - i; j++){
            int temp_2 = temp - (i + j);
            int temp_3 = arr[i + R] * arr[j + B] * arr[temp_2 + G];
            count += arr[size] / temp_3;
        }
    }
    return count;
}
int main(){
    int R = 2, G = 1, B = 1;
    int size = 4;
    cout<<"Count of number of strings (made of R, G and B) using given combination are: "<<combination(R, G, B, size);
    return 0;
}

実行結果

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

Count of number of strings (made of R, G and B) using given combination are: 12

この入力例では R＋G＋B ＝ 4 がちょうど size と一致しているため、残り文字数は0になり、答えは多項係数 4! ÷ (2! × 1! × 1!) ＝ 12 通りとして直接求まります。一方、R＋G＋B が size より小さい場合は、余った文字の配分方法を二重ループで全探索しながら各ケースの順列数を足し合わせることで、正しい総数を効率よく算出できます。