よくある文字列を後ろから処理していくと上手くいくような問題のように、見方を工夫すると楽に解ける問題について具体例を挙げつつ、この発想に慣れていく目的で書いています。
色々解法は存在すると思いますが、取り敢えず文字列を後ろから見る方法で考えて行きたいと思います。
例として'('が与えられたら末尾に')'を足すのが最善。同様に(’('の場合は末尾に))を追加する。('()の場合は、後ろから見て()まではOK、ただ次の'('が独立しているので')'を追加する。この時追加の方法として()()と('(')')の二通りが考えられるが、辞書順配列を考えると後者の方が適切。一方、'()))'のような場合は先頭に'(('を追加すれば良い（辞書順配列的に先頭の'('は問題ない）
ダラダラと記述を並べましたが、議論をまとめると末尾から見て')'の数をカウントし、これが0の状態で'('が来たらSの末尾に')'を追加、0でない時つまり'()'のようにペアが形成されている時カウントを−1する。文字列Sを全て見終わったらカウントの数だけSの先頭に'('を追加すれば目的の文字列が得られる。ソースコード例→ https://atcoder.jp/contests/abc064/submissions/5707735
(writer かっつ)
例として'('が与えられたら末尾に')'を足すのが最善。同様に(’('の場合は末尾に))を追加する。('()の場合は、後ろから見て()まではOK、ただ次の'('が独立しているので')'を追加する。この時追加の方法として()()と('(')')の二通りが考えられるが、辞書順配列を考えると後者の方が適切。一方、'()))'のような場合は先頭に'(('を追加すれば良い（辞書順配列的に先頭の'('は問題ない）
ダラダラと記述を並べましたが、議論をまとめると末尾から見て')'の数をカウントし、これが0の状態で'('が来たらSの末尾に')'を追加、0でない時つまり'()'のようにペアが形成されている時カウントを−1する。文字列Sを全て見終わったらカウントの数だけSの先頭に'('を追加すれば目的の文字列が得られる。ソースコード例→ https://atcoder.jp/contests/abc064/submissions/5707735
(writer かっつ)
