C++で増加部分列の総数をカウントする方法

はじめに

このチュートリアルでは、増加する部分列（サブシーケンス）の総数を求めるC++プログラムについて解説します。

0から9までの数字を含む配列が与えられます。私たちのタスクは、「次の要素が前の要素より大きい」という条件を満たす部分列の総数を数えることです。

アプローチ：動的計画法

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。

• 配列 count[10] を用意し、count[d] を「数字 d で終わる増加部分列の数」と定義します。
• 配列の各要素 arr[i] を順に走査します。各ステップで、arr[i] より小さい数字 j（0 〜 arr[i]-1）で終わる部分列の数をすべて合計し、count[arr[i]] に加算します。
• その後、要素 arr[i] それ自身だけからなる長さ1の部分列も数えるため、count[arr[i]] に1を加えます。
• すべての走査が完了したら、count[0] 〜 count[9] の合計が答えとなります。

計算量は O(n × 10)、つまり配列の長さに対してほぼ線形時間で処理できるため、非常に効率的な手法です。

実装例

#include<bits/stdc++.h>
using namespace std;
// 可能な部分列の数をカウントする
int count_sequence(int arr[], int n){
   int count[10] = {0};
   // 各数字を順に走査
   for (int i=0; i<n; i++){
      for (int j=arr[i]-1; j>=0; j--)
         count[arr[i]] += count[j];
      count[arr[i]]++;
   }
   // すべての可能な部分列を集計
   int result = 0;
   for (int i=0; i<10; i++)
      result += count[i];
   return result;
}
int main(){
   int arr[] = {3, 2, 4, 5, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << count_sequence(arr,n);
   return 0;
}

出力

14

動作の確認

入力 {3, 2, 4, 5, 4} の場合、答えが 14 になる理由を確認してみましょう。

• 長さ1の部分列：5個（各要素そのもの）
• 長さ2の部分列：7個（例：3→4、2→5、4→5 など）
• 長さ3の部分列：2個（3→4→5、2→4→5）

合計 5 + 7 + 2 = 14 個の増加部分列が存在することになり、プログラムの出力と一致します。

まとめ

本記事では、動的計画法を活用して増加部分列の総数を効率的に数える方法を紹介しました。各数字で終わる部分列の数を記録しながら配列を一度だけ走査するため、大規模な入力に対しても高速に動作します。同様のDPの考え方は、最長増加部分列（LIS）など他の部分列関連の問題にも応用できるので、ぜひ覚えておきましょう。