ARC141 C Bracket and Permutation

①順列Pにおいてj<iかつPj>Piなるjが存在するような $S_{Pi}$ は')'で確定です。

②同じく、順列Qにおいてj<iかつPj<Piなるjが存在するような $S_{Pi}$ は')'で確定です。

このようにして確定させた'('の個数はちょうどnでなければならないです。

'('を1、')'を-1に対応させたとき、一般に「正しい括弧列⇔累積和が常に0以上」が成り立ちます。

もしSiが')'にも関わらず①を満たさないとき、[P1,Pi]は[1,i]の並び替えになっています。 $\sum_{k=1}^{i} P_{k} \geq 0$ が成り立つので $\sum_{k=1}^{i} S_{k} \geq 0$ です。

②も満たさないとすると同様に $\sum_{k=i}^{n} S_{k} \geq 0$ です。この二つを足すと $\sum_{k=1}^{n} P_{k} +Pi \geq 0$ となりますが左辺は-1なので矛盾します。

よってSi=')'のとき上記上記の方法で必ず')'だと確定されます。

このように確定された')'以外を'('とすることでSは一つに定まります。

このようにして求めたSから貪欲に辞書順最小のもと最大のものを作り、P,Qに一致するか確認すれば終わりです。