C++で指定位置に開き括弧を含むバランスの取れた括弧式の数を数えるアルゴリズム

問題の概要

整数 m と位置情報の配列 position[]（1 ≤ length(position[]) ≤ 2m）が与えられたとき、長さ 2m の正しい（バランスの取れた）括弧式を作る方法が何通りあるかを求めます。ただし、指定された位置には必ず開き括弧「[」を置く必要があります。

注意：position[] 配列は1始まりのインデックスで表現されます。例えば [0, 1, 1, 0] のように与えられ、「1」は開き括弧を置かなければならない位置を示します。「0」の位置には、開き括弧または閉じ括弧のどちらでも置くことができます。

入出力例

入力: n = 2, position[] = [1, 0, 1, 0]
出力: 1

この場合、条件を満たす唯一の組み合わせは以下の通りです。

[ ] [ ]

本記事では、この問題を解くために再帰的なアプローチと、それを最適化するメモ化（Memoization）を使った手法について解説します。

アルゴリズムの考え方

まず、与えられた配列 adj1 内で、開き括弧を配置すべきすべての位置に「1」をマークしておきます。

その後、次のような再帰処理を実行します。

• 開き括弧の数から閉じ括弧の数を引いた値（合計カウント）が 0 より小さくなった場合は、0 を返します（不正な状態）。
• インデックスが m に達し、かつ合計カウントがちょうど 0 であれば、有効な解が見つかったので 1 を返します。そうでなければ 0 を返します。
• 現在のインデックスに予め「1」が割り当てられている場合は、開き括弧のカウントを増やしながら index+1 で再帰的に関数を呼び出します。
• それ以外の場合は、その位置に開き括弧を挿入してカウントを +1 するケースと、閉じ括弧を挿入してカウントを -1 するケースの両方について再帰的に関数を呼び出し、その結果を合計します。

再帰による実装例

上記のアルゴリズムに基づいたC++での再帰的解法は以下の通りです。

// 上記の手法を再帰で実装したC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 正しい括弧式の数を見つける関数
int find(int index1, int openbrk1, int m, int adj1[]) {
    // 開き括弧と閉じ括弧の差が0未満の場合
    if (openbrk1 < 0)
        return 0;

    // インデックスが式の末尾に達した場合
    if (index1 == m) {
        // 括弧がバランスしていれば
        if (openbrk1 == 0)
            return 1;
        else
            return 0;
    }

    // 現在のインデックスに開き括弧が割り当てられている場合
    if (adj1[index1] == 1) {
        // 開き括弧の数を増やして前へ進む
        return find(index1 + 1, openbrk1 + 1, m, adj1);
    }
    else {
        // その位置に開き括弧・閉じ括弧の両方を挿入して前へ進む
        return find(index1 + 1, openbrk1 + 1, m, adj1)
             + find(index1 + 1, openbrk1 - 1, m, adj1);
    }
}

// ドライバーコード
int main() {
    int m = 2;
    // 位置1に開き括弧を配置
    int adj1[4] = { 1, 0, 0, 0 };

    // find関数を呼び出して答えを計算
    cout << find(0, 0, 2 * m, adj1) << endl;
    return 0;
}

出力結果

2

メモ化による最適化

上記の再帰アルゴリズムでは、同じ状態が何度も計算されるため非効率です。そこでメモ化（Memoization）を導入することで、計算量を大幅に改善できます。

具体的には、配列（DPテーブル）を用意して以前の計算結果を保存しておきます。こうすることで、一度計算した値については再帰呼び出しを繰り返すことなく、保存済みの値を即座に返せるようになります。

メモ化を使用した実装例

// メモ化を実装したC++プログラム
#include <bits/stdc++.h>
using namespace std;
#define M 1000

// 正しい括弧式の数を見つける関数
int find(int index1, int openbrk1, int m,
         int dp1[M][M], int adj1[]) {
    // 開き括弧と閉じ括弧の差が0未満の場合
    if (openbrk1 < 0)
        return 0;

    // インデックスが式の末尾に達した場合
    if (index1 == m) {
        // 括弧がバランスしていれば
        if (openbrk1 == 0)
            return 1;
        else
            return 0;
    }

    // dp1に既に計算結果が保存されている場合
    if (dp1[index1][openbrk1] != -1)
        return dp1[index1][openbrk1];

    // 現在のインデックスに開き括弧が割り当てられている場合
    if (adj1[index1] == 1) {
        // 開き括弧の数を増やして前へ進む
        dp1[index1][openbrk1] = find(index1 + 1,
                                     openbrk1 + 1, m, dp1, adj1);
    }
    else {
        // その位置に開き括弧・閉じ括弧の両方を挿入して前へ進む
        dp1[index1][openbrk1] =
            find(index1 + 1, openbrk1 + 1, m, dp1, adj1) +
            find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
    }

    // 計算結果を返す
    return dp1[index1][openbrk1];
}

// ドライバーコード
int main() {
    // 答えを事前計算するためのdp1配列
    int dp1[M][M];
    int m = 2;
    memset(dp1, -1, sizeof(dp1));

    // 位置1に開き括弧を配置
    int adj1[4] = { 1, 0, 0, 0 };

    // find関数を呼び出して答えを計算
    cout << find(0, 0, 2 * m, dp1, adj1) << endl;
    return 0;
}

出力結果

2

計算量

時間計算量： O(N²)

メモ化を導入することで、指数関数的な再帰呼び出しが O(N²) まで抑えられ、大きな入力に対しても効率的に動作します。