【C++】中央値が部分集合自体にも含まれる部分集合の個数を数える方法

正の数だけを格納した配列 arr[] が与えられます。この記事のゴールは、arr[] の要素から選んだ部分集合のうち、その部分集合の値の中央値が、同じ部分集合の中にも存在するようなものの個数を求めることです。

入力例

arr[] = { 1,2,3 }

出力例

Count of number of subsets whose median is also present in the same subset are: 4

解説

中央値が同じ集合内に存在する部分集合は、次の4つです。

[ 1 ] … 中央値は 1
[ 2 ] … 中央値は 2
[ 3 ] … 中央値は 3
[ 1,2,3 ] … 中央値は 2

入力例 2

arr[] = { 4,6,5 }

出力例 2

Count of number of subsets whose median is also present in the same subset are: 4

解説

条件を満たすのは [ 4 ]、[ 6 ]、[ 5 ]、[ 4,6,5 ] の4つです。

解法のアプローチ

このアプローチでは、部分集合のサイズが奇数か偶数かを区別して扱います。

要素数が奇数の部分集合では、中央値は必ず中央に位置する要素そのものであるため、常に集合内に存在します。したがって、奇数長の部分集合の総数 2ⁿ⁻¹ を答えに加算します。

一方、要素数が偶数の部分集合では、中央値は中央に並ぶ2つの要素の平均になります。中央値が集合内に存在するためには、この2つの中央要素が同じ値でなければなりません。そこで、ソート済みの配列で隣り合う同値のペアを探し、組み合わせ nCr の計算によって条件を満たす偶数長の部分集合を数え上げます。

アルゴリズムの手順

• 正の数の配列 arr[] を受け取ります。
• 関数 median_subset(arr, size) は、中央値が同じ部分集合内にも存在する部分集合の個数を返します。
• 関数 check(int temp) は、for ループ（i = 2 ～ i <= temp）を使って引数の階乗を計算します。ループ内で count = count * i を更新し、ループ終了後に階乗として返します。
• 関数 com(int n, int r) は組み合わせ nCr の値を返します。内部では temp = check(r) * check(n − r)、temp_2 = check(n) / temp を計算し、temp_2 を返します。
• 関数 power(int n, int r) は n の r 乗（n^r）を返します。
• r が 0 であれば答えは 1 なので、1 を返します。
• total = power(n, r / 2) を計算します。
• total を total² % mod で更新します（mod = 1000000007）。
• r が奇数なら (total * n) % mod を、そうでなければ total を返します。
• median_subset() の中では、まず count = power(2, size − 1) とします。これが奇数長部分集合の総数です。
• sort(arr, arr + size) で配列をソートします。
• while ループで各要素を調べ、等しい値が連続している間、左側の中央要素を探索します。
• temp_2 = size − 1 − temp は、右側の中央要素よりも右にある要素の個数です。
• temp_3 = i は、左側の中央要素よりも左にある要素の個数です。
• count = (count + com(temp_3 + temp_2, temp_3)) % mod として、条件を満たす偶数長の部分集合をカウントに加算します。
• while ループを抜けた時点で count が確定します。
• 最後に count を結果として返します。

C++ 実装例

#include <algorithm>
#include <iostream>
using namespace std;
#define mod 1000000007;
int check(int temp){
    int count = 1;
    for (int i = 2; i <= temp; i++){
        count = count * i;
    }
    return count;
}
int com(int n, int r){
    int temp = check(r) * check(n − r);
    int temp_2 = check(n) / temp;
    return temp_2;
}
int power(int n, int r){
    if (r == 0){
        return 1;
    }
    int total = power(n, r / 2);
    total = (total * total) % mod;
    if (r % 2){
        int temp = (total * n) % mod;
        return temp;
    } else {
        return total;
    }
}
int median_subset(int* arr, int size){
    int count = power(2, size − 1);
    sort(arr, arr + size);
    for (int i = 0; i < size; ++i){
        int temp = i + 1;
        while (temp < size && arr[temp] == arr[i]){
            int temp_2 = size − 1 − temp;
            int temp_3 = i;
            count = (count + com(temp_3 + temp_2, temp_3)) % mod;
            temp++;
        }
    }
    return count;
}
int main(){
    int arr[] = { 4, 5, 4, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of number of subsets whose median is also present in the same subset are: "<<median_subset(arr, size);
    return 0;
}

実行結果

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

Count of number of subsets whose median is also present in the same subset are: 9