【AtCoder】競プロ典型90問 002 - Encyclopedia of Parentheses（★3）

002 - Encyclopedia of Parentheses（★3）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 799 / NoviSteps: 3Q / 配点: 3 点

問題概要

長さ $N$ の「正しいカッコ列」をすべて、辞書順に出力せよ。 ただし、正しいカッコ列は次のように定義される。

• ()は正しいカッコ列である
• $S$ が正しいカッコ列であるとき、文字列 ( $+S+$ ) は正しいカッコ列である
• $S,T$ が正しいカッコ列であるとき、文字列 $S+T$ は正しいカッコ列である
• それ以外の文字列はすべて、正しいカッコ列でない

また、 ( の方が ) よりも辞書順で早いものとする。

制約

• $1 \leq N \leq 20$
• $N$ は整数

考察

まずは、 $N$ の制約が非常に小さいことに注目しよう。

(, ) のみからなる長さ $N$ の文字列は $2^N$ 通り存在するが、 $2^{20} \approx 10^6$ であるから、これは全てのパターンを全探索できそうである。

このような全探索をするときは、bit 全探索が便利である。

今回は、長さ $N$ の文字列を $N$ ビットの整数で表現し、(に対応するビットを $0$ 、) に対応するビットを $1$ として扱うことにする。

例 :

• ()() → $0101$
• )))()((( → $11101000$

次に、各文字列が「正しいカッコ列」であるかどうかを判定する方法について考えよう。

ここで、ある文字列 $S$ が正しいカッコ列であるための必要十分条件は、以下の 2 つを満たすことであるという典型が存在する。

• $S$ に含まれる( の数と ) の数は等しい。
• 任意の $1 \leq k \leq |S|$ に対して、 $$\begin{equation*} (S の先頭から k 文字目までの\texttt{'('}の個数) \geq (S の先頭から k 文字目までの\texttt{')'}の個数) \end{equation*}$$

これらを満たすか判定するために、カウンタ $\mathrm{cnt}$ を用意し、文字列を左から順に見ていく。

( を見たら $+1$ 、) を見たら $-1$ とし、途中で $\mathrm{cnt} < 0$ となった or 最終的に $\mathrm{cnt} \neq 0$ となった場合は「正しいカッコ列」ではないと判定できる。

あるいは、カウンタを累積和テーブルに置き換えてもよい。

計算量は、全探索が $O(2^N)$ 、各文字列の判定が $O(N)$ であるから、全体では $O(N \cdot 2^N)$ となる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
6. 
7.// ======================================== //
8. 
9.int main()
10.{
11.    int N;
12.    cin >> N;
13. 
14.    rep(bit, 0, (1 << N))
15.    {
16.        string s;
17.        rrep(i, N - 1, 0)
18.        {
19.            if (!(bit & (1 << i)))
20.                s += "(";
21.            else
22.                s += ")";
23.        }
24. 
25.        int cnt = 0;
26.        bool flag = true;
27.        for (auto &&c : s)
28.        {
29.            if (c == '(')
30.                cnt++;
31.            else
32.                cnt--;
33. 
34.            if (cnt < 0)
35.            {
36.                flag = false;
37.                break;
38.            }
39.        }
40. 
41.        if (cnt == 0 && flag)
42.            cout << s << endl;
43.    }
44.}

https://atcoder.jp/contests/typical90/submissions/70397545

atcoder.jp

実装時間: 10 分

コメント

bit 全探索が使えると見極めるポイントと、正しいカッコ列の判定条件をしっかり理解しておきたい。