ARC141 - C. Bracket and Permutation (600)
解法
自明な必要条件を列挙すると通る。
$ P_i > P_{i + 1}のとき$ S_{P_i} =(かつ$ S_{P_i + 1} =)である。
$ Q_i < Q_{i + 1}のとき$ S_{Q_i} =(かつ$ S_{Q_i + 1} =)である。
答えが存在するなら、これによって$ Sが一意に定まることを示す。
$ Sは (, )が同数存在する。
括弧列の$ \pm 1の累積和のグラフを考える。$ Sの$ x軸より上の部分にある区間と下の部分にある区間に分かれる。
$ x軸より上にある区間だけに注目すると、対応の取れた括弧列になっている。
これに対して$ Qを求めることを考えると、次の手順が繰り返されることがわかる。
まず、最後にある(が選ばれる。
その後、最後にある) が選ばれる。ここで選ばれる位置は先ほど選んだ(より右にあることに注意。
$ x軸より上の部分は$ Q、下の部分は$ Pによって一意に定められるということである。