AOJ 2931 - 括弧を語る数 / Parentheses Number (RUPC2019 Day3 B)

解法

まず、順列 $p$ に逆の情報を持たせます。すなわち、
$i$ 番目の開き括弧が $j$ 番目の閉じ括弧に対応しているとき、数列の $i$ 番目の値は $j$ である。
というようにします。
すると、スタックを利用して、次のような操作を行うことで、問題の条件を満たす括弧列を作成することができます。
まず、今見ている配列の添え字を $i$ 、次に出現する閉じ括弧が $j$ 番目であるとします。

スタックに $p_i$ をプッシュします。と同時に、答えとなる文字列 $s$ に"("を追加します。
スタックの一番上と、 $j$ を比較します。数字が同じであれば、スタックからその数字を取り出して捨てます。そして、 $j$ を1増やして、 $s$ に")"を追加します。
2の操作が行える限り行います。スタックが空になるか、数字が一致しなくなったら1の操作に戻ります。 $p_{i}$ をすべてプッシュし終えていたら、全ての操作を終了します。