整合したカッコ列を bit 全探索する問題！！！

類題とか

問題概要

長さ $N$ の「整合したカッコ列」を辞書順にすべて列挙せよ。

整合したカッコ列の意味については、問題ページにて。

制約

$1 \le N \le 20$

考えたこと

カッコ列を 0 と 1 の列に対応させて考えよう。"(" を 0 にして、")" を 1 にするのだ。

()(( → 0100

そうすると、

カッコ列を列挙せよ → 0 と 1 の列を列挙せよ
カッコ列を辞書順に出力せよ → ビット列を整数とみなしたときに、それが小さい順に列挙せよ

という風に言い換えられる。あとは、カッコ列が整合するかどうかの確認ができれば OK。

なお、bit 全探索の部分については次の記事を。

drken1215.hatenablog.com

カッコ列の整合性判定

()((())())

みたいなカッコ列が与えられたときに、それが整合しているかどうかを確認するのは、めっちゃよく出る典型問題。次のような変数 score を用意しておこう。

score ← 今まで見た中での "(" の個数から、")" の個数を引いた値

とする。変数 score の値は、カッコ列を左から見て行って

"(" が来たら score += 1
")" が来たら score -= 1

という風にすれば OK。

そして、次のように判定できる！！

途中で score の値が負になったらダメ
- この場合は ")" に対応する "(" が枯渇したことを意味する
- 例："())(" とか
最後まで見たときに score が 0 でない場合はダメ
- この場合は "(" と ")" の個数が揃ってないことを意味する
- 例："())" とか
これらの条件をすべてクリアすれば OK
- 上図の "(()(()))()" は満たす

計算量は $O(N2^{N})$ になる (カッコ列の整合性判定に $O(N)$ かかる)。

コード (C++)

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

// カッコ列 S が整合しているかどうか
bool isvalid(const string &S) {
    int score = 0;
    for (auto c: S) {
        if (c == '(') ++score;
        else if (c == ')') --score;

        // 途中で 0 を下回るとダメ
        if (score < 0) return false;
    }
    
    // 最後に 0 なら true、そうでなければ false
    return (score == 0);
}

int main() {
    // 入力
    int N;
    cin >> N;

    // カッコ列を順に列挙していく
    for (int bit = 0; bit < (1<<N); ++bit) {
        string S = "";

        // 最上位の桁から順に見ていく
        for (int i = N - 1; i >= 0; --i) {
            if (!(bit & (1<<i))) S += "(";
            else S += ")";
        }

        // 整合していたら出力
        if (isvalid(S)) cout << S << endl;
    }
}

コード (Python3)

Python では、bit 全探索は itertools.product を使うと便利！！

from itertools import product

# カッコ列 S が整合しているかどうか
def isvalid(S):
    score = 0
    for c in S:
        if c == '(':
            score += 1
        else:
            score -= 1

        # 途中で 0 を下回るとダメ
        if score < 0:
            return False

    # 最後に 0 なら True、そうでなければ False
    return (score == 0)

N = int(input())
for S in product(['(', ')'], repeat=N):
    if (isvalid(S)):
        # リストを文字列に
        print(*S, sep='')

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

競プロ典型 90 問 002 - Encyclopedia of Parentheses（3Q, ★3）

問題概要

制約

考えたこと

カッコ列の整合性判定

コード (C++)

コード (Python3)