https://atcoder.jp/contests/abc064/tasks/abc064_d
先頭に"(", 末尾に")“を繋げて括弧列を作るのが辞書式最小となる。 (そのような作り方をしないと、より左の位置に”)“が出現する)
“(” -> +1, “)” -> -1 と文字列を置き換えて累積和を取ったものを c[i] とすると、 c[i] ≥ 0 (1≤i≤n-1), c[n] = 0 が括弧列を成立させる条件である。
https://atcoder.jp/contests/abc064/tasks/abc064_d
先頭に"(", 末尾に")“を繋げて括弧列を作るのが辞書式最小となる。 (そのような作り方をしないと、より左の位置に”)“が出現する)
“(” -> +1, “)” -> -1 と文字列を置き換えて累積和を取ったものを c[i] とすると、 c[i] ≥ 0 (1≤i≤n-1), c[n] = 0 が括弧列を成立させる条件である。