C++でK分木における重みWのパスの数を求める方法

この記事では、C++を使ってK分木（K-ary tree）における重みWのパスの数を計算する方法を解説します。K分木とは、各ノードがK個の子を持つ木構造のことであり、各エッジには重みが割り当てられています。あるノードからそのすべての子へ伸びるエッジの重みは、1からKまでの値を順に取ります。

今回求めたいのは、根（ルート）から始まるパスのうち、重みの合計がWに等しく、かつ重みM以上のエッジを少なくとも1つ含むパスの総数です。以下に具体例を示します。

入力 : W = 4, K = 3, M = 2

出力 : 6

この問題では、動的計画法（DP）を活用することで、時間計算量と空間計算量を大幅に削減できます。メモ化を取り入れれば、プログラムを格段に高速化でき、より大きな制約条件下でも実用的に動作するようになります。

アプローチ

このアプローチでは、木を再帰的に走査しながら、「重みM以上のエッジをこれまでに使用したかどうか」という情報を状態として保持します。そして、パスの重みの合計がちょうどWに等しくなった時点で、条件を満たしていれば答えを1つ増やします。これにより、同じ状態の再計算を避けながら、すべての有効なパスを効率よく数え上げることができます。

実装コード

#include <bits/stdc++.h>
using namespace std;
int solve(int DP[][2], int W, int K, int M, int used){
    if (W < 0) // Wが0未満になった場合は0を返す
        return 0;
    if (W == 0) {
        if (used) // usedが0でなければ1を返す
            return 1; // 重みM以上のエッジが少なくとも1つ含まれているため
        return 0;
    }
    if (DP[W][used] != -1) // DP[W][used]が-1でない場合は計算済みなのでその値を返す
        return DP[W][used];
    int answer = 0;
    for (int i = 1; i <= K; i++) {
        if (i >= M)
            answer += solve(DP, W - i, K, M, used | 1); // 条件を満たしたらusedを1に更新
        else
            answer += solve(DP, W - i, K, M, used);
    }
    return answer;
}
int main(){
    int W = 3; // 目標の重み
    int K = 3; // 各ノードが持つ子の数
    int M = 2; // 重み2以上のエッジを1つ以上含める必要がある
    int DP[W + 1][2]; // メモ化用のDP配列
    memset(DP, -1, sizeof(DP)); // 配列を-1で初期化
    cout << solve(DP, W, K, M, 0) << "\n";
    return 0;
}

出力

3

コードの解説

この実装のポイントは、2つの状態管理にあります。まず、重みM以上のエッジが少なくとも1回使用されたかどうかをフラグ変数usedで追跡しています。次に、残りの重みWを減らしながら再帰的に探索し、合計がちょうどWに達したときに条件判定を行います。

各ステップでは、1からKまでの重みを持つエッジを選択して再帰呼び出しを行います。選んだエッジの重みがM以上の場合は、used | 1によってフラグを立てます。最終的にW == 0かつused == 1となった経路のみをカウントすることで、「重みM以上のエッジを必ず含むパス」だけを正確に数え上げられます。また、メモ化により同一状態の重複計算を排除している点も重要です。

まとめ

この記事では、動的計画法を用いて、K分木における重みWのパスのうち、重みM以上のエッジを1つ以上含むパスの数をO(W×K)の時間計算量で効率的に求める方法を紹介しました。

再帰とメモ化を組み合わせたシンプルな実装でありながら、素朴な全探索よりもはるかに高速に動作する点が魅力です。同様の状態圧縮・メモ化のテクニックは、他の組み合わせ最適化問題にも応用できるので、ぜひ理解を深めておきましょう。