SRM714 Div1 Easy Parenthesis Removal

対応が正規の括弧列の文字列与えられる。この文字列に対し以下の操作を行う。

1. 左端の開括弧を削除
2. 除去後も括弧列が正規であるような任意の閉括弧を1個削除する

この操作を繰り返し行なった後、空文字になるパターンは何通りあるか。

括弧列の問題は後ろから考える。(以前AtCoderでも似たような問題があったのだがまたやらかしてしまった気がする)

後ろから閉じ括弧の深さでレベルをインクリメントしていき、開き括弧に当たった時点でその消し方は{現在のレベル}通りある。これが何故前から考えると駄目かというと、括弧を削除した結果、その後続にある括弧についてペアになれないものが存在することがあるからである。その点後ろから見た場合は必ず今まで見た閉じ括弧のいずれかと開括弧が組み合わせになることができる。

その為、初期値をret=1として、開括弧に当たるごとにレベルをかけていけばよい。modを忘れないこと。O(N)。