C++で単調増加数列から最大の集計値を求める方法【DFS全探索】

問題の概要

2つの整数 n と m、さらに4つの整数 {ai, bi, ci, di} を含む k 個のタプルが与えられているとします。配列 a、b、c、d の4つが入力として渡され、a[i] は i 番目のタプルの a の値を表します。

ここで、n 個の正の整数からなる狭義単調増加の数列 dp(1 ≤ dp[1] < dp[2] < … < dp[n] ≤ m)を考えます。「集計(tally)」という指標を次のように定義します。

集計 = 条件 dp[b[i]] − dp[a[i]] = c[i] を満たすすべての添字 i における d[i] の総和

該当する i がひとつも存在しない場合、集計は 0 になります。求めるのは、数列 dp の選び方の中で実現可能な最大の集計値です。

たとえば、n = 4、m = 5、k = 4、a = {2, 2, 3, 5}、b = {4, 3, 4, 6}、c = {4, 3, 3, 4}、d = {110, 20, 20, 40} が入力された場合、出力は 130 になります。

解法のアプローチ

この問題は、深さ優先探索(DFS)による全探索で解くことができます。数列 dp の各要素を左から順に昇順で決めていき、n 個すべてが確定した時点で集計値を計算し、その最大値を記録します。具体的には以下の手順に従います。

サイズ 100, 100, 100, 100, 10 の配列 A, B, C, D, dp を定義する。
関数 depthSearch(c, l) を定義する。
c が n と等しい場合:
    total := 0
    i := 0 から i < k の間、i を 1 ずつ増やしながら:
        もし dp[B[i]] - dp[A[i]] が C[i] と等しければ:
            total := total + D[i]
    res := res と total の最大値
    return
j := l から j <= m の間、j を 1 ずつ増やしながら:
    dp[c] := j
    depthSearch(c + 1, j)
i := 0 から i < k の間、i を 1 ずつ増やしながら:
    A[i] := a[i], B[i] := b[i], C[i] := c[i], D[i] := d[i]
    A[i] を 1 減らす
    B[i] を 1 減らす
depthSearch(0, 1)
return res

アルゴリズムのポイント

再帰関数 depthSearch の引数 c は「現在確定させようとしている dp の位置」、l は「その位置に入れられる最小の値」を表します。数列は狭義単調増加でなければならないため、ループの開始値を l に設定することで、重複する探索を自然に排除できます。また、入力の添字が 1 始まりであるのに対して配列は 0 始まりなので、A[i] と B[i] からあらかじめ 1 を引いておきます。

計算量について

1 以上 m 以下の値から n 個を選んで単調増加列を作る組み合わせは二項係数 C(m, n) 通りあり、各列ごとに k 個の条件を確認するため、全体の時間計算量は O(C(m, n) × k) です。n と m が小さい範囲では十分実用的ですが、値が大きくなると組み合わせが爆発的に増える点には注意しましょう。

C++ 実装例

理解を深めるために、次の実装例を見てみましょう。

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

int n, m, k, res = 0;
int A[100], B[100], C[100], D[100], dp[10]; 

void depthSearch(int c, int l){
   if(c == n){
      int total = 0;
      for(int i = 0; i < k; i++) {
         if(dp[B[i]] - dp[A[i]] == C[i]) total += D[i];
      }
      res = max(res, total);
      return;
   }
   for(int j = l; j <= m; j++){
      dp[c] = j;
      depthSearch(c + 1, j);
   }
}
int solve(int a[], int b[], int c[], int d[]){
   for(int i = 0; i < k; i++){
       A[i] = a[i], B[i] = b[i], C[i] = c[i], D[i] = d[i]; A[i]--, B[i]--;
   }
   depthSearch(0, 1);
   return res;
}
int main() {
   n = 4, m = 5, k = 4;
   int a[] = {2, 2, 3, 5}, b[] = {4, 3, 4, 6}, c[] = {4, 3, 3, 4}, d[] = {110, 20, 20, 40};
   cout<< solve(a, b, c, d);
   return 0;
}

入力

4, 5, 4, {2, 2, 3, 5}, {4, 3, 4, 6}, {4, 3, 3, 4}, {110, 20, 20, 40}

出力

130

まとめ

本記事では、単調増加数列 dp の候補を DFS で網羅的に生成し、条件を満たす d[i] の合計の最大値を求める手法を紹介しました。制約が小さい組合せ最適化問題では、シンプルな全探索が有効な選択肢になることを覚えておきましょう。