おれってどうしたらいいですか

おれってどうしたらいいですか←以前にTwitterで見かけた文言を気に入って盗用しています

競プロ典型 90 問 002 valid parens の列挙

競プロ典型 90 問 002 の解説のうち、 ngtkana さんのもので紹介されている方法がうまくいく理由を次のように考えた。

以下のことを確かめる。

操作後の列は正しいカッコ列である
辞書順で操作前と操作後の間に正しいカッコ列は無い

お断り

"("と")"からなる列 $p$ が正しいカッコ列であることと次のことは同値:

$s_p = 0$ とする。列 $p$ の左から1文字ずつ読み取り、"("ならば+1、")"ならば-1を $s_p$ に足す。以下の両方が成り立つ。

最後の文字を読み終えた時点で $s_p = 0$
最後の文字を読み終えるまで常に $s_p \geq 0$

上に出てきた $s_p$ をスコアと呼んだり、 $p$ の $i$ 文字目を読み終えた時点の $s_p$ の値を指して $s(i)$ と書いたりさせてもらう。また、列 $p$ が明らかな場面では下付き文字を省略して単に $s$ と書かせてもらう

1.を確かめる

操作の前後で"("と")"の個数は変わらないから、操作前が正しいカッコ列ならば操作後の列も先述の(a)を満たす。

以下、操作後の列が先述の(b)も満たすことを確かめる。

操作前の列 $p$ で最も右にある"())"の"("の位置を左から $i$ 文字目と呼ぶことにする。

操作後の列 $p'$ を左から $i-1$ 文字目まで、 $i$ 文字目、 $i+1$ 文字目から終わりまでの三つの部分に分けてスコアが0以上となっていることを確認する。

一つ目の部分

操作前後で左から $i-1$ 文字目までは等しいから操作後の列の左から $i-1$ 文字目まではスコアが0以上である。

二つ目の部分

操作前の列は先述の(b)を満たすことと、 $i, i+1, i+2$ 文字目が"())"という並びであることから $s_p(i-1) \geq 1$ である。

操作後の列の $i$ 文字目は")"になっているが、 $s_{p'}(i) = s_p(i-1) - 1\geq 0$ が成り立つ。

三つ目の部分

操作後の列の $i+1$ から終わりまでは"("を左、")"を右に寄せた形である。

"("が連続する間は明らかにスコアが0以上である。

")"が連続する間にスコアが0より小さくなると仮定する。

このとき、 $p'$ の $i+1$ 文字目から終わりまでの形からして $s_{p'} < 0$ となる。

一方、操作の前後で"("と")"の個数は変わらないから $s_{p} = s_{p'} = 0$ となるべきで、矛盾がある。

背理法から")"が連続する間にスコアが0より小さくなることはない

2.を確かめる

操作後の列が、 $i$ 文字目が")"な列の中では、辞書順で最も早いことは $i+1$ 文字目から終わりまでの形から明らかであり、正しいカッコ列でもある。

後は次のすべてを満たす列がないことがわかればよい:

$p$ より遅い
$i+2$ 文字目まで $p$ と等しい
正しいカッコ列

(i)と(ii)の二つを満たす列 $q$ は(iii)を満たさないことを確認する。

(i)をまじめに言い直すと、 $i+2 < j$ で $p_k = q_k$ $(k < j)$ , $p_j = ($ , $q_j = )$ を満たすものが存在する。ここで $p_j$ などは列の $j$ 文字目を表す。

(ii)より $s_q(j-1) = s_p(j-1)$

ところで $p$ について最も右の"())"より右にある"("ではスコアが1になる。まじめに書くと次が成り立つ:

$p_k = ($ かつ $i < k$ ならば $s_p(k) = 1$

なぜならば $s_p(k) > 1$ とすると、最後の文字を読み終えた時点でスコアが0になるには $k$ 文字目より右で")"が2個以上連続しなければならない。

$k$ 文字目より右で")"が2個以上連続すると、 $i, i+1, i+2$ 文字目の"())"より右にさらに"())"があることとなり、矛盾する。

背理法から $s_p(k) = 1$

"("を読んでスコアが1になるなら、その一文字前ではスコアは0である。

以上をまとめると $s_q(j-1) = s_p(j-1) = 0$ となり、 $q$ を左から読むと $j$ 文字目でスコアは負となるから $q$ は正しいカッコ列でない