Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for a, b, s in T:
        if b >= 0:
            front.append((a, b, s))
        else:
            back.append((a, b, s))

    front.sort(key=lambda x: x[0], reverse=True)
    back.sort(key=lambda x: min(0, x[0]-x[1]), reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back[::-1]:
        if m + ma < 0:
            no()
            # print("負", s)
            return
        m += mb

    if m == 0:
        yes()
    else:
        # print("非零到達")
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import cython
 
def main():
    import sys
    readline = sys.stdin.readline
    
    N: cython.longlong
    N = int(readline())
    S = [readline().strip() for i in range(N)]
    
    D = []
    L, R = [], []
    for s in S:
        l: cython.longlong = 0
        r: cython.longlong = 0
        for c in s:
            if c == ')':
                if l > 0: l -= 1
                else: r += 1
            else: l += 1
        if l == 0 and r == 0:pass
        elif l == 0: R.append(r)
        elif r == 0: L.append(l)
        else: D.append((l, r))
    
    L: cython.longlong
    R: cython.longlong
    L = sum(L)
    R = sum(R)
    
    inc = []
    dec = []
    for l, r in D:
        if l > r:
            inc.append((l, r))
        else:
            dec.append((l, r))
    
    inc.sort(key=lambda x:x[1])
    dec.sort(key=lambda x:-x[1])
    
    D = inc + dec
    
    l: cython.longlong
    r: cython.longlong
    for _, (l,r) in enumerate(D):
        L -= r
        if L < 0:
            print('No')
            exit(0)
        L += l
    
    if L == R:
        print('Yes')
    else:
        print('No')
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from cython import longlong
 
def main():
    n: longlong
    n=int(input())
    lp, lm = [], []
    for i in range(n):
        s=input()
        
        x: longlong
        y: longlong
        x,y=0,0
        
        for j in s:
            if j=="(":x+=1
            else:x-=1
            y=min(y,x)
        if x>0: lp.append((y,x))
        else: lm.append((y-x,-x))
    lp.sort()
    s: longlong
    s=0
 
    i: longlong
    j: longlong
    for i,j in lp[::-1]:
        if s+i<0:
            print("No")
            exit()
        s+=j
    lm.sort()
 
    t: longlong
    t=0
 
    i: longlong
    j: longlong
    for i,j in lm[::-1]:
        if t+i<0:
            print("No")
            exit()
        t+=j
    if s==t: print("Yes")
    else: print("No")
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    #print(locat_doubling)
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M, K = LI()
    C = combination(N,mod2)
    ans = 0
    for i in range(N):
        if i>K:
            break
        cur = C.comb(N-1,i) * M * pow((M - 1), N - i - 1, mod2) % mod2
        #print(cur)
        ans += cur
        ans %= mod2
    print(ans)
    return

def examF():
    N = I()
    LRC = [[0,0,0]for _ in range(N)]
    flag_l = False; flag_r = False
    C = 0
    for i in range(N):
        S = SI()
        cur = 0
        l = 0
        for s in S:
            if s==")":
                cur += 1
            else:
                cur -= 1
            if cur>l:
                l = cur
        LRC[i][0] = l
        if l==0:
            flag_l = True
        cur = 0
        r = 0
        for s in S[::-1]:
            if s=="(":
                cur += 1
            else:
                cur -= 1
            if cur>r:
                r = cur
        LRC[i][1] = r
        if r==0:
            flag_r = True
        LRC[i][2] = l-r
        C += l-r
    if (not flag_l) or (not flag_r):
        print("No")
        return
    if C!=0:
        print("No")
        return
    #print(LRC)
    LRC.sort(key=lambda x:x[1])
    A = [0]*N
    B = [0]*N
    #print(LRC)
    for i in range(N):
        A[i] = LRC[i][2]
        B[i] = LRC[i][0]
    now = 0
    for i in range(N):
        ne = bisect.bisect_right(B,now)-1
        now += A[ne]
        #print(now,ne)
        A[ne] = 0
    if random.random()>0.5:
        print("No")
        return
    print("Yes")
    return

def examF2():
    N = I()
    LC = []
    RC = []
    C = 0
    for i in range(N):
        S = SI()
        cur = 0
        l = 0
        for s in S:
            if s==")":
                cur += 1
            else:
                cur -= 1
            if cur>l:
                l = cur
        cur = 0
        r = 0
        for s in S[::-1]:
            if s=="(":
                cur += 1
            else:
                cur -= 1
            if cur>r:
                r = cur
        cnt = l-r
        C += cnt
        if cnt<0:
            LC.append((l,r))
        else:
            RC.append((r,l))
    if C!=0:
        print("No")
        return
    LC.sort()
    RC.sort()
    #print(LC)
    #print(RC)
    L = 0
    for nowl,nowr in LC:
        if nowl>L:
            print("No")
            #print(nowl,nowr)
            return
        L += nowr-nowl
    R = 0
    for nowr,nowl in RC:
        if nowr>R:
            print("No")
            #print(nowr,nowl,RC,R)
            return
        R += nowl-nowr
    print("Yes")
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn

5
))))(((((
(((
))))))((
)((
)

6
(()))(())(((
()((()
())
)(()()(
)))(())(((
))))()
"""

Submission status: Accepted

Solution code:
n=int(input())
s=[input() for i in range(n)]
p,m=[],[]
res=0
for i in range(n):
    lr=0
    min_=0
    for c in s[i]:
        if c=='(':
            lr+=1
        else:
            lr-=1
        min_=min(min_,lr)
    if lr>=0:
        p.append([lr,min_])
    else:
        m.append([lr,min_])
    res+=lr
if res!=0:
    print('No')
    exit()
p.sort(key=lambda x:x[1],reverse=True)
m.sort(key=lambda x:(x[0]-x[1]),reverse=True)
cum=0
for x,y in p:
    if cum+y<0:
        print('No')
        exit()
    cum+=x
for x,y in m:
    if cum+y<0:
        print('No')
        exit()
    cum+=x
print('Yes')

Submission status: Accepted

Solution code:
N = int(input())

tleft = 0
tright = 0
a = []
b=  []
for _ in range(N):
  s = input()
  left = 0
  lmin = 0
  for c in s:
    if c == "(":
      left += 1
    else: # ")"
      left -= 1
      lmin = min(lmin,left)
  #
  if left >= 0:
    if lmin == 0:
      tleft += left
    else:
      a.append([left,lmin])
  else:
    if left <= lmin:
      tright += left
    else:
      b.append([left,lmin])
#
a.sort(key=lambda x:-x[1])
b.sort(key=lambda x:x[1])

for left, lmin in a:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
for left, lmin in b:
  if tleft + lmin < 0:
    print("No")
    exit(0)
  else:
    tleft += left
#
if tleft + tright == 0:
  print("Yes")
else:
  print("No")
#

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    Ss = [input() for _ in range(n)]
    U = [[0, 0] for _ in range(n)]
    for i in range(n):
        for c in Ss[i]:
            if c == "(":
                U[i][1] += 1
            else:
                if U[i][1] == 0:
                    U[i][0] += 1
                else:
                    U[i][1] -= 1
    L, R = 0, 0
    P = []
    for i in range(n):
        if U[i][0] == 0 and U[i][1] > 0:
            L += U[i][1]
        elif U[i][0] > 0 and U[i][1] == 0:
            R += U[i][0]
        elif U[i][0] > 0 and U[i][1] > 0:
            P.append([U[i][0], U[i][1]])
    P.sort(key=lambda x: (x[0]-x[1], x[0], -x[1]))
    if L == 0 and R == 0 and len(P) == 0:
        print("Yes")
    elif (L == 0 or R == 0) and len(P) > 0:
        print("No")
    else:
        f = True
        for i in range(len(P)):
            L -= P[i][0]
            if L < 0:
                f = False
                break
            L += P[i][1]
        if L == R and f:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def determine_string_code(bracket_string):
  brackets_left = 0 # )
  brackets_right = 0 # (
  for char in bracket_string:
    if char == "(":
      brackets_right += 1
    else:
      if brackets_right > 0:
        brackets_right -= 1
      else:
        brackets_left += 1
  return (brackets_left, brackets_right)

def build_left(in_list):
  in_list.sort(key=lambda x: x[0])
  final_res = (0, 0)
  for res in in_list:
    if res[0]>final_res[1]:
      final_res = (final_res[0]+res[0]-final_res[1], res[1])
    elif res[0]<final_res[1]:
      final_res = (final_res[0], res[1]+final_res[1]-res[0])
    else:
      final_res = (final_res[0], res[1])
  return final_res

def build_right(in_list):
  in_list.sort(key=lambda x: x[1])
  final_res = (0, 0)
  for res in in_list:
    if final_res[0]>res[1]:
      final_res = (res[0]+final_res[0]-res[1], final_res[1])
    elif final_res[0]<res[1]:
      final_res = (res[0], final_res[1]+res[1]-final_res[0])
    else:
      final_res = (res[0], final_res[1])
  return final_res

n = int(input())
residues = list()
for _ in range(n):
  new_string = input()
  residues.append(determine_string_code(new_string))
first_half = list()
second_half = list()
for res in residues:
  if res[1] > res[0]:
    first_half.append(res)
  else:
    second_half.append(res)
first_res = build_left(first_half)
second_res = build_right(second_half)
if first_res[0] == 0 and second_res[1] == 0 and first_res[1] == second_res[0]:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
import bisect

n=int(input())
opens=0
closes=0
ls=[]
rs=[]
for _ in range(n):
  s=input()
  cnt1=0
  cnt2=0
  for i in range(len(s)):
    if s[i]=='(':
      cnt1+=1
    else:
      if cnt1==0:
        cnt2+=1
      else:
        cnt1-=1
  if cnt2==0:
    opens+=cnt1
  elif cnt1==0:
    closes+=cnt2
  else:
    ls.append(cnt2)
    rs.append(cnt1)
ls=sorted(ls)
rs=sorted(rs)
lefts=sum(ls)
rights=sum(rs)
if opens-closes!=lefts-rights:
  print('No')
else:
  flag=False
  if len(ls)==0:
    flag=True
  for a in ls:
    if opens<a or closes<a+(rights-lefts):
      continue
    pos=bisect.bisect_right(rs,a+(rights-lefts))
    if pos!=0:
      flag=True
      break
  for b in rs:
    if opens<b+(lefts-rights) or closes<b:
      continue
    pos=bisect.bisect_right(ls,b+(lefts-rights))
    if pos!=0:
      flag=True
      break
  if flag==True:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
import bisect

n=int(input())
opens=0
closes=0
ls=[]
rs=[]
for _ in range(n):
  s=input()
  cnt1=0
  cnt2=0
  for i in range(len(s)):
    if s[i]=='(':
      cnt1+=1
    else:
      if cnt1==0:
        cnt2+=1
      else:
        cnt1-=1
  if cnt2==0:
    opens+=cnt1
  elif cnt1==0:
    closes+=cnt2
  else:
    ls.append(cnt2)
    rs.append(cnt1)
ls=sorted(ls)
rs=sorted(rs)
lefts=sum(ls)
rights=sum(rs)
if opens-closes!=lefts-rights:
  print('No')
else:
  flag=False
  if len(ls)==0:
    flag=True
  for a in ls:
    if opens<a or closes<a+(rights-lefts):
      continue
    pos=bisect.bisect_right(rs,a+(rights-lefts))
    if pos!=0:
      flag=True
      break
  for d in rs:
    if opens<d+(lefts-rights) or closes<d:
      continue
    pos=bisect.bisect_right(ls,d+(lefts-rights))
    if pos!=0:
      flag=True
      break
  if flag==True:
    print('Yes')
  else:
    print('No')

Submission status: Accepted

Solution code:
n = int(input())
left=[]
right=[]
for i in range(n):
    s = input()
    l = len(s)
    a=0
    b=0
    a1=0
    b1=0
    for j in range(l):
        if s[j]==')':
            a1+=1
        else:
            a1-=1
        a=max(a1,a)
    for j in range(l):
        if s[l-1-j]=='(':
            b1+=1
        else:
            b1-=1
        b = max(b1,b)
    if a>b:
        right.append((a,b))
    else:
        left.append((a,b))
right.sort(key = lambda x:x[1],reverse=True)
left.sort(key = lambda x:x[0])
all = left+right

if all[0][0]>0:
    print('No')
    exit()
st = all[0][1]
for i in range(1,n):
    st-=all[i][0]
    if st<0:
        print('No')
        exit()
    st+=all[i][1]
if st>0:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n = int(input())
s = [input().strip() for _ in range(n)]
plus = []
minus = []
for i in s:
    min_v = 0
    sum_v = 0
    for j in i:
        sum_v += 1 if j == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append((min_v, sum_v))
    else:
        minus.append((min_v-sum_v, -sum_v))
 
plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)
 
sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v
 
sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v
 
if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

import sys
input = sys.stdin.readline

n = int(input())
s = [input().strip() for _ in range(n)]
plus = []
minus = []
for i in s:
    min_v = 0
    sum_v = 0
    for j in i:
        sum_v += 1 if j == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append((min_v, sum_v))
    else:
        minus.append((min_v-sum_v, -sum_v))

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

n = int(input())
s = [input() for _ in range(n)]
plus = []
minus = []
for i in s:
    min_v = 0
    sum_v = 0
    for j in i:
        sum_v += 1 if j == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append((min_v, sum_v))
    else:
        minus.append((min_v-sum_v, -sum_v))

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

n = int(input())
plus = []
minus = []
for i in range(n):
    min_v = 0
    sum_v = 0
    s = input()
    for j in s:
        sum_v += 1 if j == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append((min_v, sum_v))
    else:
        minus.append((min_v-sum_v, -sum_v))

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))

    tmp.sort(key=lambda x: (x[1] < 0, (-x[0] if x[1] >= 0 else -(x[1] - x[0]))))
    #tmp.sort(key=lambda x: (x[1] < 0, -x[0], x[1]))
    #print(tmp)

    cur = 0
    for mn, cnt in tmp:
        #print(cur, mn, cnt)
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt

    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    S = [input().strip() for _ in range(N)]
    Up = []
    Down = []
    for s in S:
        now = 0
        m = 0
        for t in s:
            if t == "(":
                now += 1
            else:
                now -= 1
            if now < m:
                m = now
            # print(t, now)
        if now >= 0:
            Up.append((m,now))
        else:
            Down.append((m-now,-now))
    up = 0
    Up.sort(reverse=True)
    for m, inc in Up:
        if up+m < 0:
            print("No")
            return
        up += inc
    
    down = 0
    Down.sort(reverse=True)
    # print(Up, Down)
    for m, dec in Down:
        if down+m < 0:
            print("No")
            return
        down += dec
    if up != down:
        print("No")
        return
    print("Yes")
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import chain

N = int(input())
zenhan = []
kouhan = []
for _ in range(N):
    si = input()
    last = 0
    low = last
    high = last
    for s in si:
        if s == "(":
            last += 1
        else:
            last -= 1
        low = min(low, last)
        high = max(high, last)
    if last >= 0:
        zenhan.append((-low, last, low))
    else:
        kouhan.append((low - last, last, low))
zenhan.sort()
kouhan.sort()

open_close = 0
for key, last, low in chain(zenhan, kouhan):
    if open_close + low < 0:
        ans = "No"
        break
    else:
        open_close += last
else:
    if open_close:
        ans = "No"
    else:
        ans = "Yes"
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

n = I()
A = []
B = []
for _ in range(n):
    s = S()
    ret = 0
    ret2 = 0
    for i in s:
        if ret and i == ')':
            ret -= 1
        elif i == '(':
            ret += 1
        else:
            ret2 += 1
    if ret2 > ret:
        A += [(ret, ret2)]
    else:
        B += [(ret, ret2)]

A.sort()
B.sort(key=lambda x:x[1], reverse=True)
L = A + B
now = 0
for x, y in L:
    if x > now:
        print('No')
        exit()
    now = now - x + y

if now:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
# input
N = int(input())
S = [input() for _ in range(N)]

# process
T = []
for s in S:
    while '()' in s:
        s = s.replace('()', '')
    T.append(s)

l1 = []
l2 = []
for t in T:
    op = t.find('(')
    if op < 0:
        op = len(t)
    cl = len(t) - op
    
    if cl+op != 0:
        if cl <= op:
            l1.append((cl, op))
        else:
            l2.append((op, cl))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if len(l1)+len(l2) == 0:
    result = True
elif len(l1)>0 and len(l2)>0 and l1[0][0]+l2[-1][0] == 0:
    for cl, op in l1:
        x -= cl
        if x < 0:
            break
        x += op
    
    if x >= 0:
        for op, cl in l2:
            x -= cl
            if x < 0:
                break
            x += op
            
        if x == 0:
            result = True

# output
print("Yes" if result else "No")

Submission status: Accepted

Solution code:
N = int(input())
if N == 1:
    st = 0
    S = input()
    for x in S:
        if x == '(':
            st += 1
        else:
            if st > 0:
                st -= 1
            else:
                print('No')
                exit()
    if st == 0:
        print('Yes')
    else:
        print('No')
    exit()
lst1, lst2 = [], []
flg, mr = 0, 10**9
for i in range(N):
    S = input()
    st, r, rall = 0, 0, 0
    for c in S:
        if c == '(':
            st += 1
        else:
            rall += 1
            if st > 0:
                st -= 1
            else:
                r += 1
    pls = max(0, len(S)-rall-(rall-r))
    if pls >= r:
        lst1.append((r, -pls))
    else:
        lst2.append((-pls, r))
lst1.sort()
lst2.sort()
if lst1[0][0] != 0:
    print('No')
    exit()
lcnt = -lst1[0][1]
for (r, pls) in lst1[1:]:
    lcnt -= r
    if lcnt < 0:
        print('No')
        exit()
    lcnt -= pls
for (pls, r) in lst2:
    lcnt -= r
    if lcnt < 0:
        print('No')
        exit()
    lcnt -= pls
if lcnt == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
N = int(input())
As = []
Bs = []

for _ in range(N):
  c = 0
  m = 0
  for s in input():
    if s == '(':
      c += 1
    elif s == ')':
      c -= 1
    m = min(m, c)
  if c >= 0:
    As.append((-m, c - m))
  else:
    Bs.append((-m, c - m))

As.sort(key=lambda x: x[0])
Bs.sort(key=lambda x: x[1], reverse=True)

f = True
c = 0
for (l, r) in As:
  if c < l:
    f = False
    break
  c += r - l
if f:
  for (l, r) in Bs:
    if c < l:
      f = False
      break
    c += r - l

f = f and (c == 0)

if f:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
n = int(input())
ss=[list(map(str,input().split())) for i in range(n)]
zenhan=[]
kouhan=[]

for i in range(n):
    retu = list(ss[i])[0]
    acnt=0
    bcnt=0
    for j in range(len(retu)):
        if retu[j] == "(":
            acnt+=1
        elif acnt>0:
            acnt-=1
    a=acnt

    acnt=0
    bcnt=0
    for j in reversed(range(len(retu))):
        if retu[j] == ")":
            bcnt+=1
        elif bcnt>0:
            bcnt-=1
    b=bcnt

    if a!=0 or b!=0:
        if a < b:
            kouhan.append([a,b,retu])
        else:
            zenhan.append([a,b,retu])

zenhan.sort(key=lambda x:x[1])
kouhan.sort(reverse=True)
cnt=0
for tmp in zenhan:
    retu=tmp[2]
    for i in range(len(retu)):
        if retu[i] == "(":
            cnt+=1
        else:
            cnt-=1
        if cnt<0:
            print("No")
            exit()

for tmp in kouhan:
    retu=tmp[2]
    for i in range(len(retu)):
        if retu[i] == "(":
            cnt+=1
        else:
            cnt-=1
        if cnt<0:
            print("No")
            exit()
if cnt!=0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
S_s = [input() for _ in range(N)]
S_data1 = []
S_data2 = []
for S in S_s:
    life = 0
    A=0
    for c in S:
        if c == '(':
            life += 1
        else:
            if life > 0:
                life -= 1
            else:
                A += 1
    if(A<life):
        S_data1.append(tuple([A,life]))
    else:
        S_data2.append(tuple([A,life]))
S_data1.sort()
S_data2 = sorted(S_data2, key=lambda x:-x[1])
S_data1.extend(S_data2)
S_data = tuple(S_data1)
life = 0
answer = True
for S_datum in S_data:
    life -= S_datum[0]
    if life < 0:
        answer = False
        break
    life += S_datum[1]
else:
    if life != 0:
        answer = False

if answer:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#from collections import defaultdict, deque
#import itertools
#import numpy as np
#import re
import bisect

def main():
    N = int(input())
    SS = []
    for _ in range(N):
        SS.append(input())
    S = []
    for s in SS:
        while '()' in s:
            s = s.replace('()', '')
        S.append(s)
    #print(S)
    S = [s for s in S if s != '']
    sum_op = 0
    sum_cl = 0
    S_both_op = []
    S_both_cl = []
    for s in S:
        if not ')' in s:
            sum_op += len(s)
        elif not '(' in s:
            sum_cl += len(s)
        else:
            pos = s.find('(')
            if pos <= len(s) - pos:
                S_both_op.append((pos, len(s)-pos))  #closeのほうが少ない、'))((('など -> (2,3)
            else:
                S_both_cl.append((pos, len(s)-pos))  #closeのほうが多い、')))(('など -> (3,2)

    # S_both_opは、耐えられる中でより伸ばす順にしたほうがいい？
    #S_both_op.sort(key=lambda x: (x[0], x[0]-x[1]))  #closeの数が小さい順にsortかつclose-openが小さい=伸ばす側にsort
    #S_both_cl.sort(key=lambda x: (x[0], x[0]-x[1]))  #これもcloseの数が小さい順にsortかつclose-openが小さい=あまり縮まない順にsort
    S_both_op.sort(key=lambda x: x[0])
    S_both_cl.sort(key=lambda x: -x[1])

    for p in S_both_op:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]

    for p in S_both_cl:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    
    if sum_op == sum_cl:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3


def countpars(s):
    lc = 0
    rc = 0
    for ch in s:
        if ch == '(':
            lc += 1
        else:
            if lc > 0:
                lc -= 1
            else:
                rc += 1
    return (lc, rc)


n = int(input())

ssl = []
ssr = []
for i in range(n):
    (clc, crc) = countpars(input())
    if clc >= crc:
        ssl.append((clc, crc))
    else:
        ssr.append((clc, crc))

ssl.sort(key=lambda x: x[1])
ssr.sort(reverse=True)

lc = 0
rc = 0

for (clc, crc) in ssl:
    lc -= crc
    if lc < 0:
        print('No')
        exit()

    lc += clc

for (clc, crc) in ssr:
    lc -= crc
    if lc < 0:
        print('No')
        exit()
    lc += clc
        

if lc == 0:
    print('Yes')
else:
    print('No')