C++で積がK未満となる部分列の個数を求める方法

このチュートリアルでは、積がK未満となる部分列(サブシーケンス)の個数を求めるプログラムについて解説します。

問題設定は次のとおりです。非負の整数からなる配列と値kが与えられたとき、配列の要素を選んで構成できる部分列のうち、要素の積がk未満になるものの総数を求めます。

動的計画法によるアプローチ

この問題は動的計画法(DP)を使うことで効率的に解けます。ここでは、dp[i][j] を「先頭からj個の要素の中から選んだ部分列のうち、積がi未満になるものの個数」と定義します。

遷移は次のように考えます。まず、j番目の要素 arr[j-1] を部分列に含めない場合の数は dp[i][j-1] です。次に、含める場合は、その要素を末尾に追加した形の部分列が新たに数え上がるため、dp[i / arr[j-1]][j-1] + 1 を加算します。なお、ゼロ除算を避けるため、arr[j-1] が0より大きい場合のみこの遷移を行います。

サンプルコード

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

// 積がk未満の部分列を数える関数
int count_sub(vector<int> &arr, int k){
    int n = arr.size();
    int dp[k + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            // arr[j-1] を含まない場合
            dp[i][j] = dp[i][j - 1];
            // arr[j-1] を含む場合
            if (arr[j - 1] <= i && arr[j - 1] > 0)
                dp[i][j] += dp[i / arr[j - 1]][j - 1] + 1;
        }
    }
    return dp[k][n];
}

int main(){
    vector<int> A;
    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);
    int k = 10;
    cout << count_sub(A, k) << endl;
}

実行結果

11

出力の解説

上記の例では、配列 {1, 2, 3, 4} と k = 10 が与えられています。積が10未満となる部分列は、次の11個です。

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

例えば {3,4} の積は12でk以上となるため除外され、{1,2,3} の積は6、{1,2,4} の積は8なので条件を満たします。DPテーブルの最終的な答え dp[10][4] が11となり、正しく個数が求まっていることが確認できます。

計算量

時間計算量・空間計算量はいずれも O(k × n) です。kが非常に大きい場合はメモリ使用量に注意が必要ですが、典型的な制約条件下では全部分列を列挙する指数時間のアプローチよりはるかに効率的です。