はじめに
はじめまして。nauclhlt (X: @hourai_night)と申します。Qiitaで記事を書くのにはまだ慣れていないため、変な部分があったらすみません。この記事では備忘録も兼ねて括弧列についてまとめています。
記事内で使用する記号を示します:
- 文字列 $S$ に対して、$S$ の長さを $|S|$ と表す
- 文字列 $S$ に対して、$S$ の $i$ 文字目を $S_i$ と表す
全く一般的ではないですが、簡単のため次の用語を用います:
- 括弧列 $S$ に対して、
(を $1$、)を $-1$ に対応させて並べた数列を $S$ のバランス列と呼ぶ - 括弧列 $S$ に対して、$S$ のバランス列 $A$ に対してその累積和、つまり $L_i=\sum_{k=1}^{i} A_k$ を満たす数列 $L$ を $S$ の累積和と呼ぶ
1. 定義
(この記事で)括弧列とは()(())のような文字列を指します。呼び方にはいくつかのバリエーションが存在し、単に括弧列というほかに、対応が取れた括弧列、バランスが取れた括弧列、正しい括弧列などと呼ばれます。ここでは単に括弧列と呼ぶことにします。
括弧列の定義にも少しバリエーションが見られます。
定義1
括弧列は以下のルールにしたがって構成される
- 空文字列
- ある括弧列 $S$ が存在して、
(、$S$、)をこの順に結合した文字列 - ある括弧列 $S, T$ が存在して、$S$、$T$をこの順に結合した文字列
定義2
- 文字列 $S$ は、$S$ に連続部分文字列として含まれる
()を取り除く操作を0回以上繰り返して$S$を空文字列とすることが可能なとき、またそのときに限って、括弧列である
定義3
- 文字列 $S$ は以下をすべて満たすとき、またそのときに限って、括弧列である
- $S$ に含まれる
(と)の個数は等しい - 任意の $k(1\leq k\leq |S|)$ に対して、($S$ の $k$ 文字目までに含まれる
(の個数)$\geq$($S$の$k$文字目までに含まれる)の個数)が成り立つ
- $S$ に含まれる
定義4
- 文字列 $S$ は、$S$ に
+と1を好きな位置に、好きな数だけ適切に挿入することで正しい数式を作ることができるとき、またそのときに限って括弧列である
もしかしたらこれら3つ以外の定義がされることもあるかもしれません。定義1、定義2、定義3、定義4を満たす文字列の集合は等しいです。
体感ですが、AtCoderでは定義1が最も主流であるように思います。定義4はCodeforcesで見られました。
2. 判定問題
次のような問題を考えます。
ある文字列 $S$ が与えられます。
$S$ が括弧列であるかを判定してください。
解法
定義3をもとに考えれば、$O(N)$ で解くことができます。
- はじめ $x=0$ とする。$i=1, 2, \cdots, |S|$ の順に次を行う。
- $S_i=$
(なら、 $x\leftarrow x+1$ とする - $S_i=$')'なら、$x\leftarrow x-1$ とする。この操作の後 $x=-1$ なら答えを
Noとして終了する
- $S_i=$
- 最後に、$x=0$ なら答えは
Yes、$x\neq 0$ なら答えはNoとする
正当性
定義3を考えます。$x$ は常に、($i$ 文字目までに含まれる(の個数)$-$($i$ 文字目までに含まれる)の個数)を保持します。よって、$x\lt 0$ となることがあれば1つ目の条件に違反します。よってNoです。また、最後に $x=0$ を満たすことは2つ目の条件を表します。
同様の考え方で解ける問題: ABC394-D
3. 数え上げ
次のような問題を考えます。
正整数 $N$ が与えられます。
長さ $N$ の括弧列がいくつあるかを求めてください。
定義より、括弧列は必ず偶数長です。(そうでなければ、定義3の2つ目の条件を満たさないため) したがって、$N$ が奇数なら答えは$0$です。
$N$ が偶数のときを考えます。
素朴な解法
簡単な動的計画法(DP)で数えられます。
- $dp[i][j]:=$長さ$i$の
(と)からなる文字列のうち、(含まれる(の数)$-$(含まれる)の数$=j$を満たすものの個数 - $dp[0][0]=1$
- $dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]$と遷移する。ただし、$dp[i-1][-1]=0, dp[i-1][N+1]=0$
判定問題と同じ考え方をすると、求める値は $dp[N][0]$ です。
これで、$O(N^2)$ の解法が得られました。
同様の考え方で解ける問題: ABC312-D
カタラン数
長さが $N(N: 偶数)$ である括弧列の個数は $\frac{N}{2}$ 番目のカタラン数に一致することが知られています。そしてその値は $O(N)$ で計算できるため、$O(N)$ の解法が得られます。
4. 括弧列とカタラン数の対応
カタラン数とは
カタラン数は組み合わせ理論における重要な数列とされていて、多種多様な数え上げの問題において現れます。例えば、次に示す場合の数はすべて $N$ 番目のカタラン数に一致します。
- $xy$ 平面上を、隣接する格子点への移動を繰り返して $(0, 0)$ から $(N, N)$ まで移動する最短経路のうち、直線 $y=x$ よりも上にある点を通らないものの個数
- $N-1$ 人が参加するトーナメント(つまり、$N$ 頂点の二分木)の総数
- 凸 $N+2$ 角形の頂点を両端とする互いに非交差な線分 $N$ 本を引いていくつかの三角形に分割するとき、分け方の総数
括弧列との関係
先述の通り、長さ $2n$ の括弧列の個数はカタラン数列を $\lbrace C_n\rbrace$ として $C_n$ 個です。
1の性質を考えれば簡単に理解することができます。括弧列を左から見たとき、(を $x$ 軸の正の方向に $1$、)を $y$ 軸の正の方向に $1$ 進むことに対応させれば、括弧列と $1$ のような経路に一対一対応が作れます。
また、漸化式を考えることからも分かります。カタラン数は以下の漸化式を満たします。
$$C_n=\sum_{k=0}^{n-1} C_kC_{n-k - 1}$$
長さ $2n$ の括弧列 $S$ を考えます。$S$ は括弧列の性質から、ある括弧列 $X, Y$ を用いて( $X$ ) $Y$ のように一意に分解できます。ここで、$X$ の長さを $2k$ とすると $Y$ の長さは $2n-2k-2$ となります。したがって、$X$ としてあり得るものの個数は $C_k$、$Y$ は $C_{n-k-1}$ です。$X$ の長さは $0$ から $2n-2$ までを取り得るので、それぞれ足し上げれば上の漸化式に一致することが分かります。
5. 累積和の条件
次のような問題を考えます。
長さ $N$ の括弧列 $S$ が与えられます。
$S$ の連続部分文字列として含まれる括弧列の個数を求めてください。
- $1\leq N\leq 2000$
$N\leq 2000$ なので、すべての区間を試すことができます。したがって、適切な前計算などを行うことで $S$ のある区間が括弧列であるかどうかを $O(1)$ や $O(\log N)$ で判定できればよいことになります。実際、そのようなことは可能です。
定義3から、次の事実が従います。
- $S$の累積和 $A$ をとる
- 任意の $k(1\leq k\leq N)$ に対して $A_k\geq 0$ かつ $A_N=0$ ならば $S$ は括弧列である
よって、以上のことを連続部分列に対しても高速に判定できればよいです。上と同様に $S$ の累積和 $A$ を構築します。これは $O(N)$ で可能です。$S$ の区間 $[l, r]$ が括弧列であることは次で判定できます：
- $\displaystyle \left( \min_{l\leq i\leq r} A_i\right)\geq A_l$かつ$A_{l-1}=A_r$
ただし、$A_0=0$とする
これは上の判定に加えて、$A_l$ が基準となるように考えれば明らかです。処理すべきは区間最小値ですが、これはSparse Tableを用いれば前計算 $O(N\log N)$ クエリ $O(1)$、セグメント木を用いれば前計算 $O(N)$ クエリ $O(\log N)$ で可能です。
よって、上述の問題は全体 $O(N^2)$ で解けました。
同様の考え方で解ける問題: ABC223-F
6. 括弧列を構成する手続き
上述の累積和の条件を言い換えます。長さ $2N$ の文字列 $S$ (ここで $S$ は(と)のみからなるとします) の累積和を $L$ とすると
- 任意の $i(1\leq i\leq 2N)$ に対して $L_i\geq 0$ かつ $L_{2N}=0$
が $S$ が括弧列である条件でした。
言い換えると、
- 任意の $i(1\leq i\leq 2N)$ に対して、$S$ の $i$ 文字目までに $\lceil \frac{i}{2}\rceil$ 個の
(が含まれる - $S$ に含まれる
(はちょうど $N$ 個
となります。
ここで、上の条件を満たすように左から括弧列を構成していく以下の手続きを考えられます。
- はじめ、$S$ を
)のみからなる長さ $2N$ の文字列とし、集合 $I$ を空集合としておく - $S_1\leftarrow$
(とする - $k=1, 2, \cdots, N-1$ に対して、順に次を行う
- $I$ に $2k$ および $2k+1$ を追加する
- その後、$x\in I$ なる $x$ をひとつ選び、$I$ から削除する。$S_x\leftarrow$
(と更新する
以上の手続きについて、上の条件を満たしていることは明らかであり、$S$ の文字を(に変える回数がちょうど $N$ 回であることから下の条件も満たします。よって、この手続きによって生成される $S$ は括弧列です。逆に任意の長さ $2N$ の括弧列がこの手続きによって生成され得ることも括弧列の条件から容易に確認できます。
同様の考え方で解ける問題: ABC407-E
7. 一意な分解
カタラン数のパートでも述べた通り、任意の括弧列 $S$ に対して、ある括弧列 $X, Y$ が存在して $S$ は ( $X$ ) $Y$ と表されます。この性質を用いて、サイズがより小さい括弧列2つを考えることが有効なことがあります。
同様の考え方で解ける問題: yukicoder No. 3146
8. 根付き木との対応
括弧列のネストの関係を木に対応させることができます。深さ $0$ の括弧に対して頂点 $0$ を親とすれば、根付き木になります。例えば、()(()())を考えれば、
o
/ \
o o
/ \
o o
のような木が対応します。
これにより、具体的には木DPなどの解法を適用することができることがわかります。
9. 2分木との対応
括弧列と二分木は一対一対応します。括弧列 $S$ に対応する木を $T(S)$ とおきます。このとき、以下のようにして二分木を対応させます。
- $S$ が空文字列のとき、$T(S)$ は単一の頂点のみからなる
- $S$ が空文字列でないとき、$S=$
($X$)$Y$ を満たす括弧列 $X, Y$ をとって、$T(S)$ を $T(X), T(Y)$ の根を子に持つ頂点を根とする二分木とする
このような対応は、カタラン数で数えられることからも理解できます。これは、例えば簡単な木の同型判定などに利用できます。
おわり
不備などあったらごめんなさい。