積がK以下になる部分列の個数を数える――C++での再帰的アプローチ

はじめに

このチュートリアルでは、与えられた配列の中から積がK以下になる部分列(サブシーケンス)の個数を求めるプログラムをC++で解説します。

具体的には、配列と値Kが与えられ、その積がK以下となる空でない部分列が何個存在するかを数えるのが目的です。

アプローチのポイント:対数変換

積をそのまま計算してKと比較すると、値が急激に巨大化しオーバーフローを起こす恐れがあります。そこで本手法では、次のような工夫を行います。

• 配列の各要素を log2 で対数に変換し、積の問題を和の問題に帰着させる
• Kも log2(K) に変換し、「積 ≤ K」という条件を「対数の和 ≤ log2(K)」として扱う
• 再帰的に部分列を構築しながら、条件を満たさない部分列(棄却されるもの)の個数を数える
• 最終的な答えは「全部分列数(2^n − 1) − 棄却数」として求める

枝刈りによる高速化

再帰関数内では接頭辞和(prefix sum)を活用し、無駄な探索を打ち切ります。

• 現在の和に以降の全要素を足してもKを超えない場合は、その部分木に棄却対象が存在しないため探索しない
• 現在の和がすでにKを超えている場合は、残りの要素を選ぶ/選ばないに関わらず必ず条件違反になるため、2^(n−i) 通りをまとめて棄却としてカウントする

サンプルコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//棄却される部分列の個数を保持
discard_count;
ll power(ll a, ll n){
    if (n == 0)
        return 1;
    ll p = power(a, n / 2);
    p = p * p;
    if (n & 1)
        p = p * a;
    return p;
}

//再帰的に棄却される部分列を数える
void solve(int i, int n, float sum, float k,
           float* a, float* prefix){
    //すでに和がkを超えている場合、
    //残りの選び方はすべて棄却対象
    if (sum > k) {
        discard_count += power(2, n - i);
        return;
    }
    if (i == n)
        return;
    //インデックスi以降の要素の総和
    float rem = prefix[n - 1] - prefix[i];
    //a[i]を含む場合に超える可能性があれば探索
    if (sum + a[i] + rem > k)
        solve(i + 1, n, sum + a[i], k, a, prefix);
    //a[i]を含まない場合に超える可能性があれば探索
    if (sum + rem > k)
        solve(i + 1, n, sum, k, a, prefix);
}

int countSubsequences(const int* arr, int n, ll K){
    float sum = 0.0;
    float k = log2(K);          //閾値も対数に変換
    float prefix[n], a[n];
    for (int i = 0; i < n; i++) {
        a[i] = log2(arr[i]);    //各要素を対数に変換
        sum += a[i];
    }
    prefix[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
    ll total = power(2, n) - 1;  //全部分列数
    //全体の和がすでにk以下なら、すべての部分列が条件を満たす
    if (sum <= k) {
        return total;
    }
    solve(0, n, 0.0, k, a, prefix);
    return total - discard_count;
}

int main() {
    int arr[] = { 4, 8, 7, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    ll k = 50;
    cout << countSubsequences(arr, n, k);
    return 0;
}

出力

9

処理結果の解説

配列 {4, 8, 7, 2}、K = 50 の場合、空でない部分列は合計 2^4 − 1 = 15 通り存在します。このうち積が50を超えるのは、{8, 7}、{4, 8, 7}、{4, 8, 2}、{4, 7, 2}、{8, 7, 2}、{4, 8, 7, 2} の6通りです。したがって、条件を満たす部分列の個数は 15 − 6 = 9個となります。

計算量と注意点

最悪ケースの時間計算量は O(2^n) ですが、prefix sumによる枝刈りのおかげで、実際の探索範囲は大幅に削減されます。また、対数を float 型で扱っているため、厳密な判定が求められる場面では double の使用や微小な誤差(イプシロン)の許容など、精度面への配慮を検討してください。