C++で異なる要素の数が最大となる部分列の個数を求める方法

整数のみを含む配列 arr[] が与えられます。この問題の目的は、「異なる要素（ユニークな要素）の数が最大になる」ような配列 arr[] の部分列が全部で何通りあるかを求めることです。

例えば、配列が [4, 1, 2, 3, 4] の場合、条件を満たす部分列は [4, 1, 2, 3] と [1, 2, 3, 4] の2つになります。

入力例と出力例で理解する

入力 − arr[] = { 1, 3, 5, 4, 2, 3, 1 }

出力 − 異なる要素が最大となる部分列の個数 − 4

説明 − 異なる要素は 1、2、3、4、5 の5種類です。条件を満たす部分列は次の4通りになります。

[ 1, 3, 5, 4, 2 ]、[ 3, 5, 4, 2, 1 ]、[ 5, 4, 2, 3, 1 ]、[ 1, 5, 4, 2, 3 ]。

入力 − arr[] = { 5, 4, 2, 1, 3 }

出力 − 異なる要素が最大となる部分列の個数 − 1

説明 − すべての要素が重複なく一意であるため、部分列は配列自身の1通りのみとなります。

プログラムで使用するアプローチ

このアプローチでは、まず「すべての要素が一意であれば、部分列の数は配列自身を表す1になる」という性質を利用します。一方、重複した要素が存在する場合、同じ要素のうちのどれを部分列に含めるかによって別々の部分列が生まれるため、各重複要素ごとに組み合わせが増えていきます。

そこで、各要素の出現回数（頻度）を unordered_map に記録し、すべての頻度を掛け合わせることで、異なる要素が最大となる部分列の総数を効率的に求めることができます。

• 整数型の配列 arr[] を入力として受け取ります。

• 関数 Max_distinct_subseq(int arr[], int size) は、配列とそのサイズを受け取り、異なる要素が最大となる部分列の個数を返します。

• 初期値として count を 1 に設定します。すべての要素が一意であれば、配列自身が最大の異なる要素を持つ部分列となるためです。

• 各要素の頻度を格納するために、unordered_map<int, int> 型の変数 hash を作成します。

• for ループで配列を走査し、hash[arr[i]]++ によって各要素 arr[i] の頻度を更新します。

• 次に、for ループでハッシュを走査します。各頻度（イテレータ it の it->second）を取得し、直前の count に掛け合わせます。同じ要素が x 個ある場合、それぞれが異なる部分列に含まれ得るためです。

• 最終的に count には、求めたい部分列の総数が格納されます。

• 結果として count を返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
    int count = 1;
    unordered_map<int, int> hash;
    for (int i = 0; i < size; i++){
       hash[arr[i]]++;
    }
    for (auto it = hash.begin(); it != hash.end(); it++){
       count = count * (it->second);
    }
    return count;
}
int main(){
    int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
    return 0;
}

出力

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

Count of subsequences having maximum distinct elements are: 3

この配列では要素 3 が3回出現し、その他の6つの要素（7、1、5、6、9）はそれぞれ1回ずつ出現しています。したがって、答えは 3 × 1 × 1 × 1 × 1 × 1 × 1 = 3 となり、実行結果と一致します。