ABC063 D - Insertion

問題
提出コード

解法

基本的に、"("を追加するのは文頭、")"を追加するのは末尾で大丈夫です。
正しい括弧列Xと任意のYが存在したとき、
"("を追加すべきパターンは X)Y, )XY, XY)
のようなパターン(最後のパターンのみ、Yも正しい括弧列という条件付き)で、どれも文頭に"("を加えるだけで今見ている箇所は正しくなります。
")"のパターンも同様です。
(YX, Y(X, YX(
というパターンがあり(最初のパターンのみ、Yも正しい括弧列)で、末尾に")"を加えれば今直したい箇所が正しくなります。
ということで、追加すべき括弧の個数がわかれば、あとは
(((.... S .....))))
と出力するだけです。
追加すべき"("の個数をa、初期値は0です。そして、まだ")"と対応してない"("の個数をcとします。こちらも初期値は0です。1文字目から順番に見ていきます。

• 次に見た文字が"("だった場合
  cに1追加します。

• 次に見た文字が")"だった場合
  cが1以上であれば、"("と対応させることができるので、cから1減らします。
  そうでなかった場合は、調整が必要になるので、aに1追加します。cはそのままです。

この操作を繰り返すと、最終的に追加すべき"("の個数はaに、そしてcが最終的に追加すべき")"の個数になります。
a回"("を出力、そしてSを出力して、最後にc回")"を出力すれば答えとなります。