C++で最小・最大要素を除いたサイズKのすべての部分列の積を求める方法

問題概要

n個の整数を含む配列 arr[n] と、部分列のサイズを指定する整数 k が与えられたとき、最小要素と最大要素を除いたすべてのサイズ k の部分列の積を求めて出力することが課題です。

例として、4つの要素からなる集合 {1, 2, 3, 4} と k = 2 を考えてみましょう。この場合の部分集合は以下の6つになります。

{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}

最大要素である 4 と最小要素である 1 を除外すると、残る要素は次の通りです。

2, 3, 3, 3, 2

これらの積を計算すると:

2 × 3 × 3 × 3 × 2 = 108

同様の手順でこの問題を解いていきます。

入出力例

入力: arr[] = {3, 4, 1, 7}, k = 3
出力: 144
説明: 部分集合は {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
最大値 7 と最小値 1 を取り除くと:
{3, 4}, {4}, {3}, {3, 4}
これらを掛け合わせると:
3 * 4 * 4 * 3 = 144

入力: arr[] = {1, 2, 3, 4}, k = 3
出力: 36

解法アプローチ

この問題には複数の解き方があります。ひとつは、考えられるすべての部分列を順に生成し、それぞれの集合から最大値と最小値を除いた要素の積を求める方法です。この方法は実装が簡単ですが、計算量が非常に膨大になり、非効率です。

そこで、より効率的なアプローチを紹介します。まず、部分集合として採用されるかどうかに関わらず、配列全体をソートします。

次に、各要素の出現回数を数えていきます。

ある数は C(n−1, k−1) 個の部分列に出現します。そのうち、その部分列の最大要素として現れるのは C(i, k−1) 回、最小要素として現れるのは C(n−i−1, k−1) 回です。

したがって、ソート後の i 番目の要素が「最大でも最小でもない」状態で出現する回数は、次の式で表せます。

C(n−1, k−1) − C(i, k−1) − C(n−i−1, k−1)

この方法なら、全部分列を列挙することなく各要素の出現回数を直接計算できるため、はるかに効率的です。

あとは各要素 arr[i] に対して上記の指数を求め、累乗を計算します。指数が非常に大きくなるため、高速なべき乗計算にはフェルマーの小定理を活用するとよいでしょう。

注意: 答えは非常に大きな値になる可能性があるため、10⁹+7 で割った剰余として出力します。

アルゴリズム

開始
ステップ1 → 二項係数(組み合わせ)を計算する関数を宣言
    void pairs(int a, int b)
    int i, j を宣言
    ループ For i = 0 かつ i <= a かつ i++
        ループ For j = 0 かつ j <= min(i, b) かつ j++
            IF (j == 0 || j == i)
                c[i][j] = 1 を設定
            End
            Else
                c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val を設定
            End
        End
    End
ステップ2 → べき乗を計算する関数を宣言
    LL power(LL x, unsigned LL y)
    unsigned LL temp = 1 を宣言
    x = x % val を設定
    ループ While (y > 0)
        IF (y & 1)
            temp = (temp * x) % val を設定
        End
        y = y >> 1 を設定
        x = (x * x) % val を設定
    End
    return temp % val
ステップ3 → すべての部分列の積を計算する関数を宣言
    unsigned LL product(LL arr[], int size, int k)
    unsigned LL temp = 1 を宣言・設定
    配列をソート sort(arr, arr + size)
    LL pow = c[size - 1][k - 1] を宣言・設定
    ループ For i = 0 かつ i < size かつ i++
        LL pow_l = c[i][k - 1] を宣言・設定
        LL pow_f = c[size - i - 1][k - 1] を宣言・設定
        LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val を宣言・設定
        unsigned LL mul = power(arr[i], pow_e) % val を宣言・設定
        temp = ((temp % val) * (mul % val)) % val を設定
    End
    return temp % val
ステップ4 → main() 内で
    pairs(100, 100) を呼び出す
    LL arr[] = { 3, 4, 1, 7 } を宣言・設定
    サイズを計算 int size = sizeof(arr) / sizeof arr[0]
    int k = 3 を宣言・設定
    unsigned LL temp = product(arr, size, k) を宣言・設定
    temp を出力
終了

C++実装例

#include <bits/stdc++.h>
using namespace std;
#define val 1000000007
#define LL long long
#define max 101
LL c[max - 1][max - 1];
LL power(LL x, unsigned LL y) {
    unsigned LL temp = 1;
    x = x % val;
    while (y > 0) {
        if (y & 1) {
            temp = (temp * x) % val;
        }
        y = y >> 1;
        x = (x * x) % val;
    }
    return temp % val;
}
void pairs(int a, int b) {
    int i, j;
    for (i = 0; i <= a; i++) {
        for (j = 0; j <= min(i, b); j++) {
            if (j == 0 || j == i)
                c[i][j] = 1;
            else
                c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;
        }
    }
}
// すべての部分列の積を計算する関数
unsigned LL product(LL arr[], int size, int k) {
    unsigned LL temp = 1;
    // 配列をソート
    sort(arr, arr + size);
    LL pow = c[size - 1][k - 1];
    for (int i = 0; i < size; i++) {
        LL pow_l = c[i][k - 1];
        LL pow_f = c[size - i - 1][k - 1];
        LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;
        unsigned LL mul = power(arr[i], pow_e) % val;
        temp = ((temp % val) * (mul % val)) % val;
    }
    return temp % val;
}
int main() {
    // すべての二項係数を事前計算
    pairs(100, 100);
    LL arr[] = { 3, 4, 1, 7 };
    int size = sizeof(arr) / sizeof arr[0];
    int k = 3;
    unsigned LL temp = product(arr, size, k);
    cout<<"product of all subsequences of size k except minimum and maximum element is :"<<temp << endl;
    return 0;
}

出力結果

product of all subsequences of size k except minimum and maximum element is :144

まとめ

この記事では、配列から最小要素と最大要素を除いたサイズKのすべての部分列の積を求める方法を解説しました。全部分列を列挙する素朴な手法は計算コストが膨大になりますが、配列をソートしたうえで二項係数により各要素の出現回数を求め、フェルマーの小定理を利用した高速なべき乗計算と組み合わせることで、効率的に答えを導くことができます。