一般論

• 開き括弧を右上、閉じ括弧を左下として、ジグザグなパスを作ったとき、始点も終点もy=0かつ、途中の点がy≥0 となるのが、正しい括弧列である必要十分条件

  • yの値は (開き括弧の数) - (閉じ括弧の数) だと思ってもよい。

• 括弧からなる文字列は、

  • ( を +1
  • ) を -1

  に置き換えると考えやすいし、実装しやすい。

括弧列の場合の数

• 長さ $2n$ の括弧列の長さはカタラン数 $C_n = \frac{1}{n+1}\binom{2n}{n}$ に対応する
  • 導出: $C_n = \sum_{k=0}^{n-1}C_kC_{n-1-k}$ という漸化式が括弧列の場合の数について成り立つことから
• 問題例
  • ABC 312 D - Count Bracket Sequences

括弧列にする

• ( と ) からなる文字列をカッコ列にするためには、折れ線で考えたときにy座標が

  • 最後の値が0になっているか
  • 最小値が0以上か

  が大事。

• 最後の値が0（2種類の括弧の数が同じ）になるようにした後に、最小値を上げていくしていくイメージ。

• ( と ) の数が同じ場合は、( はできるだけ左側、) はできるだけ右側にいる方がカッコ列になりやすい

  • その方が折れ線のy座標の値が大きくなるから。

• 変換（書き換え）と交換を折れ線グラフで表した場合の図

• 数列の要素を交換をした場合の累積和の変化

• 問題例

  • ARC 175 B - Parenthesis Arrangement
  • 整合した括弧列にせよ | アルゴ式
  • ABC 167 F - Bracket Sequencing
  • ARC 172 C - Election

括弧列の対応

• Stack を使えばよい。
• ABC 350 F - Transpose