C - Bracket and Permutation Editorial by chinerist
\(P_{2i-1} > P_{2i}\) のとき、 \(S_{P_{2i-1}}=\) (, \(S_{P_{2i}}=\) ) であることがわかります（もしそうでないなら \(P_{2i-1},\ P_{2i}\) を swap できてしまうからです）。同様に \(Q_{2i-1} < Q_{2i}\) のとき、\(S_{Q_{2i-1}}=\) (, \(S_{Q_{2i}}=\) ) です。
実はこの考察のみで \(S\) の候補が高々 \(1\) つにならない場合は条件を満たす \(S\) は存在しません。
証明
簡単のため \(S\) が「正しい括弧列」、または「正しい括弧列」を逆にしたものである場合を考えます。一般の \(S\) も「正しい括弧列」と「正しい括弧列」を逆にしたものの和で表せることなどから同じ方法で証明できます。
\(S\) は「正しい括弧列」であるものとします。 \(S_i=\) ( を満たす \(i\) を \(L_1 < L_2 < \dots < L_N\) 、\(S_i=\) ) を満たす \(i\) を \(R_1 < R_2 < \dots < R_N\) と置きます。\(S\) は「正しい括弧列」であるため \(L_i < R_i\) が成り立ちます。よって \(S\) に対し \(S_{p_1}S_{p_2}\dots S_{p_{2N}}\) が「正しい括弧列」となるような辞書式順序で最大の \(p\) は \(p=(L_N,\ R_N,\ L_{N-1},\ R_{N-1},\ \dots,\ L_1,\ R_1)\) となります。このとき \(S\) は \(Q\) から上の考察だけで復元できます。
\(S\) が「正しい括弧列」を逆にしたものの場合も同様に \(P\) から復元できます。
上の考察で \(S\) の候補を \(1\) つに絞った後は実際に貪欲法で \(P,\ Q\) にあたるものを構築し、一致するかを確認すればいいです。
posted:
last update: