Skip to content →

括弧列の性質

正規括弧列の定義

正規括弧列とは、

  • 空文字列
  • 二つの正規括弧列 \(A, B\) を連結した文字列 \(AB\)
  • 正規括弧列 \(A\) を用いて \((A)\) と書ける文字列

の形で表される文字列である。
正規括弧列の条件は \((\), \()\) を \(+1, -1\) に置き換えた数列 \(a\) の総和が \(0\) かつ \(a\) の累積和を取った数列 \(s\) の最小値が \(0\) と言い換えられる。つまり、\(s_i :=\sum_{k=1}^i a_k\) と置くと、
\begin{eqnarray}
\left\{
\begin{array}{l}
s_{i+1} – s_i\in \{+1,-1\} \\
s_i \geq 0 \\
s_{0} = s_{2N} = 0
\end{array}
\right.
\end{eqnarray}である。mod 2 で考えると、初めて \(s_i < 0\) となるのは \(i\) が奇数のときだけだと分かる。従って、\(s_{2i + 1} \geq 0\) で十分。

  • 長さ 2N の配列 a について、先手と後手は交互に次の操作をする。
    • 先手はまだ選ばれていない要素のうち、最も先頭に近いものを ( に置換する。
    • 後手はまだ選ばれていない要素から好きなものを ) に置換する。

    それ以上操作できなくなったとき、正しい括弧列になっていることを示せ。(ARC138C)

  • \(i\) 文字目が ‘(‘ ならば \(p_i\) 点、’)’ ならば \(-p_i\) 点を得る。長さ \(2N\) の正規括弧列の場合、得点は最大何点か(えこってさんの提出より)。【正規括弧列の条件の言い換え2】
    ‘(‘, ‘)’ を \(0, 2\) で置き換えた数列 \(b\) の累積和を取った数列 \(t\) を用いると、正規括弧列の条件は\begin{eqnarray}
    \left\{
    \begin{array}{l}
    t_{i+1} – t_i\in \{0,2\} \\
    t_i \geq i \\
    t_{0} = 0 \\
    t_{2N} = 2N
    \end{array}
    \right.
    \end{eqnarray}と言い換えられる。\(t_i \geq i\) は \(t_{2i-1} \geq 2i\) と同値であり、\(2i+1\) 文字目までに ‘(‘ が \(i\) 個以上あることを表している。
    \(p \cdot a = p \cdot b-2N\) なので、\(p\) と \(b\) の内積の最大値を求めればよい。明らかに、\(i=1,3,5,\ldots,\)に対して、順に \(t_i \geq i+1\) を満たすように、\(1,2,\ldots, i\) のうちまだ採用していない添え字であって、\(p_i\) 最大のものを ‘(‘ に置き換えるのが最適である。
  • ‘(‘, ‘)’, ‘x’ からなる長さ \(2N\) の文字列であって、’x’ を除くと、正しい括弧列になる文字列を考える。\(i\) 番目が ‘(‘ ならば \(p_i\) 点、’x’ ならば \(0\) 点、’)’ ならば \(-p_i\) 点を得る。最大何点を得るか(ABC250G)。'(‘, ‘x’, ‘)’ を \(0, 1, 2\) に置き換えた数列 \(a\) の累積和を取った数列 \(s\) を用いると、問題の文字列の条件は
    \begin{eqnarray}
    \left\{
    \begin{array}{l}
    s_{i+1} – s_i\in \{0,1,2\} \\
    s_i \geq i \\
    s_{0} = 0 \\
    s_{2N} = 2N
    \end{array}
    \right.
    \end{eqnarray}と言い換えられる。\(s, p\) の内積を最大化すればよい。\(a\) を \(0\) で初期化する。明らかに、\(i=1, 2, \ldots, \) について順に \(s_i \geq i\) が等号で成り立つように、まだ2回採用していない \(1, 2, \ldots, i\) のうち \(p_k\) が最大のものを選び、\(a_k \leftarrow a_k + 1\) とすればよい。

カッコ列の i 番目を ( から ) に変更する操作は、区間 [i:] に -2 を足す操作に、) から ( に変更する操作は +2 を足す操作に相当する。また、i番目の(とj番目の)をswapする操作は区間[i:j)に-2を足す操作に相当する。i番目が)でj番目が(ならば+2。

  • 正しい括弧列となる部分文字列の個数を求めよ。2018 codeFlyer 本選 C
  • 正しいカッコ列となるような巡回シフトのシフト幅の取り方の個数が最大となるように、一度だけ文字をswapせよ。(CF594B)

正規括弧列の個数

長さ \(2n\) の正規括弧列は $$\frac{1}{n+1}{2n \choose n}$$個ある。この数を \(n\) 項目のカタラン数と呼ぶ。\(C_{n+1}=\frac{2(2n+1)}{n+2}C_n\) に従って計算すれば、\(O(n)\) で列挙できる。

カタラン数の導出1(鏡像法)

( を →, ) を ↑ に対応させると、括弧列はグリッド上の移動と同一視できる。長さ \(2n\) の正しい括弧列は、\(y = x + 1\) を通らずに \((0, 0)\) から \((n, n)\) に移動する経路である。その経路数は鏡像法によって、\({2n \choose n}-{2n \choose n-1}\) だと分かる。\(y = x + A\) を通らずに移動する経路数は同様に鏡像法により \({2n \choose n}-{2n \choose n-A}\) である。壊れた括弧列を直す方法の数え上げで必要になることがある。

カタラン数の導出2(組合せ)

\(1, -1\) がそれぞれ \(n\) 個の列は \({2n \choose n}\) 個ある。ここから正しくない括弧列を取り除く。次の二つの個数が等しいことを全単射を構成して示す。

  1. 累積和の min が負の、\(1, -1\) がそれぞれ \(n\) 個の列
  2. \(1, -1\) がそれぞれ \(n-1, n+1\) 個の文字列

(i → ii, ii → i) 累積和が初めて \(-1\) になった箇所を \(k\) として、\(k + 1\) 文字以降の正負を反転させる。
(ii) の個数は簡単に計算でき、カタラン数は \({2n \choose n}-{2n \choose n-1}\) 個となる。

カタラン数の導出3(Bertrand’s ballot theorem)

\(+1, -1\) がそれぞれ \(n+1, n\) 個の列 \(a\) は \({2n+1 \choose n}\) 個ある。そのうち、先頭の数字を除くと正規括弧列になるのは、累積和の min が 1 であるような列である。各列について、cyclic shift したとき、そのような条件を満たす位置は一つしかない。cyclic shift で移り合う列全体を同値類とみなすと、正規括弧列の個数は $$\frac{1}{2n+1}{ 2n+1 \choose n} = \frac{1}{n+1}{2n \choose n}$$ 個であることが分かる。

カタラン数の導出4(Chung-Feller) :

Young-Ming Chen: The Chung-Feller theorem revisited, Discrete Mathematics 308 (2008), 1328–1329 による証明。

  • \(\varphi^{} : L)A(R \mapsto A(L)R\)
    • \(L\) は正規括弧列、\(A\) は負正規括弧列
  • \(\varphi^{-1} :A(L)R \mapsto L)A(R\)
    • \(L\) は正規括弧列、\(A\) は負正規括弧列

上記の \(\varphi, \varphi^{-1}\) は互いに逆写像の関係にあり、\(\varphi\) を作用させると負正規括弧列の長さが \(2\) 減る。従って、負正規括弧列の長さで同値類を作ると、各同値類の大きさは等しい。正規括弧列は負正規括弧列の長さが \(0\) の同値類をなすから、\(\frac{1}{n+1}{2n \choose n}\) 個ある。

カタラン数の母関数

接頭辞が正しい括弧列となる最初の部分で分けて、\((A)B\) のようにする。\(A, B\) もまた正しい括弧列だから、\(A\) と \(B\) の長さを \(2i, 2(n-i-1)\) とすると
$$C_{n}=\sum_{i=0}^{n-1} C_i C_{n-1-i}$$ が成り立つ。カタラン数の母関数を \(f\) とすると、\(f = 1 + xf^2\) であり、二次方程式の解の公式より、\(f = \frac{1 \pm \sqrt{1-4x}}{2x}\) となる。\(f(0) = 1\) より \(f = \frac{1- \sqrt{1-4x}}{2x}\) である。一般化二項係数によって展開すると、\begin{align}
f &= -\frac{1}{2}\sum_{i=1}^\infty {\frac{1}{2} \choose i}(-4)^ix^{i-1} \\
&=\sum_{i=1}^\infty -\frac{1}{2}\frac{1}{2}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right) \cdots \left(-\frac{2i-1}{2}\right)(-4)^i\frac{1}{i!}x^{i-1} \\
&=\sum_{i=1}^\infty\frac{1}{2}\cdot1\cdot3\cdot5\cdots (2i-1) 2^i \frac{1}{i!} x^{i-1} \\
&=\sum_{i=1}^\infty\frac{1}{2}\frac{(2i)!}{i!i!} x^{i-1} \\
&=\sum_{i=1}^\infty C_{i-1} x^{i-1} \\
\end{align} となる。

括弧列 s について、s[i]=(, s[j]=), i > j を満たすペア (i, j) の個数を転倒数と定義する。長さ 2n の括弧列全てについて、転倒数を足し上げた値を求めよ。(第5回ドワンゴからの挑戦状)

$$D_n=\sum D_iC_{n-1-i} + C_iD_{n-1-i} + i(n-i) C_i C_{n-1-i}$$を形式的べき級数で整理する。

カタラン数の畳み込み

k 個畳み込んだカタラン数を
$$C^k_n=\sum_{n=\sum_{i=1}^k n_i} \prod_{i=1}^k C_{n_i}$$
と置く。例えば \(C_n^4\) は正規括弧列 \(A, B, C, D\) (空文字列を許す) の組であって、長さの和が \(2n\) であるものの個数に等しい。

\(1,-1\) がそれぞれ \(n, n+k-1\) 個からなる列であって累積和の min が \(-(k-1)\) であるようなものを考える。
累積和の min が更新される文字を削除し、その位置で列を分割すると、累積和の min が \(0\) の \(k\) 個の区間に分けられる。
各区間を一つの正規括弧列と一対一対応させると、\(C_n^k\) と個数が等しくなる。

\(C_n^4\) の場合、\(A)B)C)D\) という ) が 3 つ多い括弧列を考えている。

導出(組合せ)

\(1, -1\) がそれぞれ \(n, n+k-1\) 個の列は \({2n+k-1 \choose n}\) 個ある。ここから正しくない括弧列を取り除く。
次の二つの個数が等しいことを全単射を構成して示す。

  1. 累積和の min が \(-k\) 以下の \(1, -1\) がそれぞれ \(n, n+k-1\) 個の列
  2. \(1, -1\) がそれぞれ \(n-1, n+k\) 個の文字列

(i → ii, ii → i) 累積和が初めて \(-k\) になった箇所を \(i\) として、\(i + 1\) 文字以降の正負を反転させる。

(ii) の個数は簡単に計算できて、$$C_n^k={2n+k-1 \choose n}-{2n+k-1 \choose n-1}$$ となる。
(KUPC2020M, yuki1662)

正しくない括弧列

正しくない括弧列 \(S\) は極大な正しい括弧列 \(A_1, A_2, \ldots, A_n\) を用いて $$S = A_1)A_2)\ldots)A_k(\ldots(A_{n-1}(A_n$$ の形に一意にできる。(を +1, ) を -1 に変換した数列 a の総和を s(S), a の累積和を取った時の最小値を m(S) とすると、) の個数は \(L(S)=-m\) に等しく、( の個数は \(R(S)=s-m\) に等しい。S に何らかの操作をして、正しい括弧列にするための最小操作数は、この形で考えると見通しが良いことが多い。 \(S, T\) に対する \(L, R, |\cdot|\) から \(S+T\) のそれが \(O(1)\) で計算でき、モノイドになる。従って、セグメント木に乗る。

  • 正しい括弧列となる部分列の長さの最大値
  • 正しい括弧列となるために必要な最小の削除回数
  • 正しい括弧列となるために必要な最小のswap回数
  • 正しい括弧列となるために必要な最小の隣接swap回数
  • 正しい括弧列となるために必要な最小の次の操作数:区間を選び、並びを逆にした後、( を ) に、) を ( にする(CodeSprint13D, SRM688Div1Easy)
  • ?, (, ) からなる文字列について、? を置き換えることで正しい括弧列にできるか。(MUJIN2016D)
    • この問題については、\begin{eqnarray}
      \left\{
      \begin{array}{l}
      t_{i+1} – t_i\in \{0,2\} \\
      t_i \geq i \\
      t_{0} = 0 \\
      t_{2N} = 2N
      \end{array}
      \right.
      \end{eqnarray}で考えるという方針でも見えやすいと思う。

いくつかの文字列を並び替えて連結したあと、正しい括弧列になるように削除すべき文字の個数は次のように最小化できる。

\(\sum a_i \geq 0\) ならば \(\min(a_i)\) の降順につなげる。
\(\sum a_i \leq 0\) ならば \(\min(a_i)\) の昇順につなげる。

(ABC167F, AOJ2681, yuki684)

正しくない括弧列は、(正規括弧列)と(逆から読むと正規括弧列)が交互に現れる列で表せる。これは、累積和の正負で区間を分割していることに相当する(ARC141C)。

ジグザグをイメージする

  • 巡回シフトで正しい括弧列にできるか線形で判定せよ (ARC138C)
  • 巡回シフトで正しい括弧列にできるなら、そのうち、辞書順最小のものを求めよ(VK Cup 2015 Round 1 : A)
  • 辞書順最小/最大の正規括弧列となるように並び替えよ(ABC141C)

木にする

長さ2nの括弧列は葉がn+1個の二分木(子の順序を区別する)と次のように一対一対応する。

  • 空文字列は一頂点からなる木に対応する。
  • 正しい括弧列 A, B を用いて (A)B と書ける括弧列は、根の右子/左子の部分木が A, B が表す二分木となる二分木に対応する。

しかし、これを考察で使う問題は見たことがない。空でない極小な括弧列 \(A_1, A_2, \ldots, A_n\) を用いて \(A_1A_2\ldots A_n\) と書ける括弧列を、根の子の部分木が \(A_1, A_2, \ldots, A_n\) の表すそれである木に対応させて、木のテクニックで解く問題は何問か出題されている。

  • 木のLCAに対応させる。(yuki1778)
  • 二乗の木DP(DDCC2016C)

()を除く(葉を除く)

空文字列を例外とし、正しい括弧列には()が存在する。()を取り除いても正しい括弧列は、なお正しい括弧列であるから、数学的帰納法に利用できる。前述の対応させた木において、葉から操作していることに対応する。

  • 対応する括弧の添字は偶奇が異なることを示せ。
  • N 箇所を白、N 箇所を黒で塗った長さ2Nの配列について、白と黒がペアになる括弧列が存在することを示せ。(ARC120D)
  • 添字の集合 \(\{1,2,\ldots,N\}\) を2つの集合 A, B に分ける。A の偶数と奇数の個数は等しく、B の偶数と奇数の個数も等しい。A に含まれる添字の位置では { か }, B に含まれる添字の位置では ( か ) となるように正しい括弧列が構成できることを示せ(AGC048B, CF1593G)

正しい括弧列の交差

\(a \leq b \leq c \leq d\) について、\(S[a .. c]\) と \(S[b..d]\) が正規括弧列ならば、\(S[a..b), S[b..c], S(c..d]\) は正しい括弧列になる(SRM688Div1Medium)。

2つのカッコ列の差分

同じ長さの2つの正しい括弧列を各位置で比較すると、文字が同じ/異なる箇所は偶数個ずつある。これは、(を+1, )を-1に変換した数列の総和が0より、差分の総和も零であることから従う。

  • 2つのカッコ列について、添字 i の文字が異なるなら \(a_i\), 同じなら \(b_i\) 点貰える。得点の最大値を求めよ。a, b の一点更新クエリあり。(CODE FESTIVAL 2017 Elimination Tournament : C)

正しい括弧列を保ったまま括弧を移動する方法

  • 長さ2nの括弧列について、先頭から i 個目の ( に対応する ) は L[i] 文字以上 R[i] 文字以下離れていることが分かっている。そのような文字列を構成せよ。(CF288Div2E)

正しい括弧列 A, B を用いて (AB) となる括弧列と (A)B となる括弧列では、 A, B を構成する括弧同士の距離は変わらない。従って、)の添字を極小に取ると、前から順に決めていき、括弧が閉じられるなら、閉じるという貪欲法が回る。

区間のreverse

区間をreverseすると、ジグザグを上下左右反転した形になる。

  • 何回reverseすると正規括弧列になるか(CF1685)
  • 辞書順最小の正規括弧となる並びが P, 最大となる並びが Q の括弧列を構成せよ。(ABC141C)

reverseすると正しい括弧列になる文字列を負正規括弧列と呼ぶことにする。

よく分かっていないもの

SRM 688 Div1 Hard
ネストの深さ d に対して sumf(d) を最小化するような分け方。証明なし

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA