Skip to content →

括弧列の性質

正しい括弧列の条件

正規括弧列とは、

  • 空文字列
  • 二つの正規括弧列 A, Bを連結した文字列 A + B
  • 正規括弧列 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}
である。

  • 長さ 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 の正しい括弧列は、y = x + 1 を通らずに (0, 0) から (n, n) に移動する経路である。その経路数は鏡像法によって、\({2n \choose n}-{2n \choose n-1}\) だと分かる。y = x + A を通らずに移動する経路数は同様に鏡像法により \({2n \choose n}-{2n \choose n-A}\) である。壊れた括弧列を直す方法の数え上げで必要になることがある。

カタラン数の導出

一つは鏡像法によって求める方法である。もう一つは上手い組合せ的解釈を見つける方法である。( が n 個、) が n 個の文字列は \({2n \choose n}\) 個ある。ここから正しくない括弧列を取り除く。初めて ( が ) より一つ多くなった箇所(括弧列として正しくなくなった箇所)を k として、k + 1 文字以降を反転する。S[k+1:] には ) が一つ多く含まれているので、S[k+1:] を反転した T[k+1:] には ( が一つ多く含まれている。従って、S[:k]+T[k+1:] には ( が n-1 個、) が n+1 個含まれている。( が n-1 個、) が n+1 個の括弧列と全単射をなすので、カタラン数は \({2n \choose n}-{2n \choose n-A}\) 個。\(C_n=\frac{2(2n+1)}{n+2}C_n\) に従って計算すれば、\(O(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) = 0\) より \(f = \frac{1- \sqrt{1-4x}}{2x}\) である。

括弧列 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 であるものの個数に等しい。A)B)C)D という ) が 3 つ多い括弧列を考えるのがミソである。A)B)C)Dは ( が n 個、) が n+3個からなる。それらをA)B)C)Dの形であるかか気にせず並べる方法は \({2n+3 \choose n}\) 通り。A)B)C)D)…となり、初めて )が ( より 4個多くなった箇所(含まない) 以降を反転する。すると全単射になる。よって、\(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)
  • ?, (, ) からなる文字列について、? を置き換えることで正しい括弧列にできるか。(mujin_pc_2016_d)

いくつかの文字列を並び替えて連結したあと、正しい括弧列になるように削除すべき文字の個数は次のように最小化できる。
(1) \(m(S) \geq 0, s(S) \geq 0\) ならば優先して先につなげる。
(2) \(m(S) < 0, s(S) \geq 0\) ならば m(S) の大きい順に繋げる。
(3) \(m(S) < 0, s(S) < 0\) ならば
\(m(S+T)=\min(m(S),m(T)+s(S))\)
\(m(T+S)=\min(m(T),m(S)+s(T))\)
なので\(m(T)+s(S),m(S)+s(T)\) の比較のみすれば良く、\(s(S)-m(S)\) の降順につなげる。
(ABC167F, AOJ2681, yuki684)

ジグザグをイメージする

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

木にする

長さ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 を構成する括弧同士の距離は変わらない。従って、)の添字を極小に取ると、前から順に決めていき、括弧が閉じられるなら、閉じるという貪欲法が回る。

よく分かっていないもの

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

Published in データ構造

Comments

コメントを残す

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

CAPTCHA