ABC 167 F - Bracket Sequencing

問題

( と ) からなる $n$ 個の文字列 $S _ i$ を適当な順番に連結して、余りなくすべての括弧が閉じられている状態にできるか判定せよ。（$n\leq 10 ^ 6, \ \sum _ {i} | S _ i | \leq 10 ^ 6$）

atcoder.jp

解説

( と ) からなる文字列中の () という部分は無視してよいので、() が存在すれば削除するという操作を繰り返すことで、各 $S _ i$ は ) の個数 $A _ i$ と ( の個数 $B _ i$ を用いて $(A _ i,B _ i)$ と表す。例えば、()))(())( は () の削除を繰り返して ))( になるので $(2,1)$ と表す。すると、$S _ i$ を適当な順番に連結してすべての括弧が閉じられている状態にできることは $(A _ i,B _ i)$ を適当な順番に並び替えて、途中で一度も $0$ 未満にならずに $$ - A _ 0 + B _ 0 - \cdots -A _ {n -1} + B _ {n - 1} = 0 $$ となること、と言い換えることができる。
この条件をみたすための最適な順番は、$- A _ i + B _ i > 0$ なる $(A _ i,B _ i)$ について $A _ i$ の昇順、$- A _ i + B _ i \leq 0$ なる $(A _ i,B _ i)$ について $B _ i$ の降順にソートし、結合したものになる。この順番が最適であること、つまりこの順番が条件をみたさないならすべての順番が条件をみたさないことは以下のように証明できる。
ある $k$ について、 $$ \sum _ {i = 0} ^ {k - 1} (- A _ i + B _ i) - A _ k < 0 $$ と仮定し、番号の順番を任意に固定する。

• $- A _ k + B _ k > 0$ の場合
  $k \leq i$ かつ $- A _ i + B _ i > 0$ なる $i$ の中で、固定した順番で最初に来るものを $j$ とする。このとき $j$ よりも前に置かれた番号の集合を $P$ とすると、すべての $i \in P$ について $i < k$ または $- A _ i + B _ i \leq 0$ なので、 $$ \sum _ {i \in P} (- A _ i + B _ i) \leq \sum _ {i = 0} ^ {k - 1} (- A _ i + B _ i) $$ さらに $k \leq j$ かつ $- A _ j + B _ j > 0$ なので、$A _ k \leq A _ j$ より、 $$ \sum _ {i \in P} (- A _ i + B _ i) - A _ j \leq \sum _ {i = 0} ^{k - 1} (- A _ i + B _ i) - A _ k < 0 $$ となり、条件をみたさない。

• $- A _ k + B _ k \leq 0$ の場合
  $i \leq k$ かつ $- A _ i + B _ i \leq 0$ なる $i$ の中で、固定した順番で最後に来るものを $j$ とする。このとき $j$ よりも後に置かれた番号の集合を $P$ とすると、すべての $i \in P$ について $i > k$ または $- A _ i + B _ i > 0$ なので、 $$ \sum _ {i \in P} (- A _ i + B _ i) \geq \sum _ {i = k + 1} ^ {n - 1} (- A _ i + B _ i) $$ さらに $j \leq k$ かつ $- A _ j + B _ j \leq 0$ なので、$B _ j \geq B _ k$ より、 $$ \sum _ {i \in P} (- A _ i + B _ i) + B _ j \geq \sum _ {i = k + 1} ^ {n - 1} (- A _ i + B _ i) + B _ k $$ また、$\displaystyle \sum _ {i = 0} ^ {n - 1} (- A _ i + B _ i) = 0$ より、 $$ \sum _ {i \notin P, i \neq j} (- A _ i + B _ i) - A _ j \leq \sum _ {i = 0} ^ {k - 1} (- A _ i + B _ i) - A _ k < 0 $$ となり、条件をみたさない。

実装

n = int(input())
L, R = [], []
for i in range(n):
    a, b = 0, 0
    for c in input():
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    if -a + b > 0:
        L.append((a, b))
    else:
        R.append((a, b))
L.sort(key=lambda x: x[0])
R.sort(key=lambda x: x[1], reverse=True)
x = 0
for a, b in L + R:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

atcoder.jp