解答：Submission #13137686 - AtCoder Beginner Contest 167
解法：'('でインクリメント、')'でデクリメントする変数lを準備する。各文字列についてこの変数が途中でとりうる最小値、最終値のタプル(m, f)が肝となる。
f ≧ 0 の文字列については、mが大きい順に結合してゆくのが良い。文字列(mi, fi)を結合する際は、結合直前のlがl + mi ≧ 0であれば結合可能であり、結合後は l = l + fiとなる。
f < 0 の文字列はその後結合してゆく。これはlの推移を逆から見るとf ≧ 0の場合と同様である。これは、文字列を反転させかつ括弧を逆にした文字列でl, m, fを計測するのと同じである。このとき、新たな文字列のlの「最小値」、「最終値」(m', f') は元の文字列の(m, f)を用いて(m - f, -f)と表される。よってこの(m', f')を用いて同様のことをチェックすればよい。
なお最終的なlが0になることを別途確認する必要がある。自分のコードではlの合計を直接計算している。
kmjpさんのブログを参考にしました。
