開き括弧を右上、閉じ括弧を左下として、ジグザグなパスを作ったとき、始点も終点もy=0かつ、途中の点がy≥0 となるのが、正しい括弧列である必要十分条件
括弧からなる文字列は、
(
を +1)
を -1に置き換えると考えやすいし、実装しやすい。
(
と )
からなる文字列をカッコ列にするためには、折れ線で考えたときにy座標が
が大事。
最後の値が0(2種類の括弧の数が同じ)になるようにした後に、最小値を上げていくしていくイメージ。
(
と )
の数が同じ場合は、(
はできるだけ左側、)
はできるだけ右側にいる方がカッコ列になりやすい
変換(書き換え)と交換を折れ線グラフで表した場合の図
数列の要素を交換をした場合の累積和の変化
問題例