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:
def CNT(A):
    tmp, Min = 0, 0
    for a in A:
        if a == '(': tmp += 1
        else: tmp -= 1
        Min = min(Min, tmp)
    return (-Min, tmp-Min)

N = int(input())
S = [input() for _ in range(N)]
T = [CNT(s) for s in S]

pls = []
mis = []
for l, r in T:
    if l <= r: pls.append((l, r))
    else: mis.append((l, r))

pls.sort(key=lambda a: a[0])
mis.sort(key=lambda a: a[1], reverse=True)
totl= pls + mis

levl = 0
for l, r in totl:
    levl -= l
    if levl < 0:
        print('No')
        exit()
    levl += r

print('Yes' if levl==0 else 'No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
S = [input()[:-1] for _ in range(N)]
rl1, rl2 = [], []

for Si in S:
    l, r = 0, 0
    
    for i in range(len(Si)):
        if Si[i]=='(':
            l += 1
        else:
            if l==0:
                r += 1
            else:
                l -= 1
    
    if l-r>=0:
        rl1.append((r, l))
    else:
        rl2.append((r, l))
    
rl1.sort(key=lambda t: t[0])
rl2.sort(key=lambda t: t[1], reverse=True)
rl3 = rl1+rl2
bal = 0

for r, l in rl3:
    bal -= r
    
    if bal<0:
        print('No')
        exit()
    
    bal += l

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

Submission status: Accepted

Solution code:
from itertools import chain
import sys

def main():
    N = int(input())
    # TLEs were caused mostly by slow input (1s+)
    # S = list(input() for _ in range(N))
    S = sys.stdin.read().split('\n')
    print(solve(S))

def get_count(args):
    s, result = args # messy input to work with map.
    cum_sum = 0
    for c in s:
        if c == ')':
            cum_sum -= 1
        else:
            cum_sum += 1
        result[0] = max(result[0], -cum_sum)
    result[1] = result[0] + cum_sum
    return result

# Made-up name, don't remember what to call this. Radix-ish
def silly_sort(array, value_min, value_max, get_value):
    if len(array) == 0:
        return
    cache = [None for _ in range(value_max - value_min + 1)]
    for elem in array:
        # Assume elem[0] is the value
        value = get_value(elem) - value_min
        if cache[value] is None:
            cache[value] = []
        cache[value].append(elem)
    for values in cache:
        if values is None:
            continue
        for value in values:
            yield value

def solve(S):
    counts = [[0,0] for _ in range(len(S))]
    counts = list(map(get_count, zip(S,counts)))
    first_group = []
    second_group = []
    min_first_group = float('inf')
    max_first_group = 0
    min_second_group = float('inf')
    max_second_group = 0

    for c in counts:
        if c[0] - c[1] <= 0:
            first_group.append(c)
            max_first_group = max(max_first_group, c[0])
            min_first_group = min(min_first_group, c[0])
        else:
            second_group.append(c)
            max_second_group = max(max_second_group, c[1])
            min_second_group = min(min_first_group, c[1])
    first_group = silly_sort(first_group, min_first_group, max_first_group, lambda c: c[0])
    second_group = reversed(list(silly_sort(second_group, min_second_group, max_second_group, lambda c: c[1])))

    order = chain(first_group, second_group)

    cum_sum = 0
    for c in order:
        cum_sum -= c[0]
        if cum_sum < 0:
            return 'No'
        cum_sum += c[1]
    if cum_sum == 0:
        return 'Yes'
    return 'No'

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip() for _ in range(N)]

A = []
B = []

for s in S:
    a = 0
    k = 0
    for i in range(len(s)):
        if s[i] == ')':
            k += 1
        else:
            k -= 1
        a = max(a, k)
    b = 0
    k = 0
    for i in range(len(s))[::-1]:
        if s[i] == '(':
            k += 1
        else:
            k -= 1
        b = max(b, k)
    A.append(a)
    B.append(b)

L = []
R = []

for i in range(N):
    if B[i] - A[i] >= 0:
        L.append((A[i], i))
    else:
        R.append((B[i], i))

L.sort()
R.sort(reverse=True)

T = []

for a, i in L:
    T.append(S[i])

for b, i in R:
    T.append(S[i])

T = ''.join(T)

k = 0

for t in T:
    if t == '(':
        k += 1
    else:
        k -= 1
    if k < 0:
        print('No')
        break
else:
    if k == 0:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
    s=input()
    l=0
    o=0
    for c in s:
        if c=='(':
            l+=1
        else:
            l-=1
            o=min(o,l)
    A.append((l,o))
A.sort(key=lambda x:-10**9 if x[1]==0 else -x[1] if x[0]>=0 else 10**7+x[1]-x[0])
last=0
for l,o in A:
    if last+o<0:
        print("No")
        exit(0)
    last+=l
print("Yes" if last==0 else "No")

Submission status: Accepted

Solution code:
# +1/-1の折れ線で表したとき
# 「0で終わる」かつ「途中で0未満にならない」を満たせば良い

# あとは貪欲を上手い事使う


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((up-down, down, up))

    a.sort(reverse=True)
    b.sort(key=lambda a: a[0],reverse=True)

    c = 0

    for d, u in a:
        if c+d < 0:
            print('No')
            break
        else:
            c += u
    else:
        for _, d, u in b:
            if c+d < 0:
                print('No')
                break
            else:
                c += u
        else:
            if c == 0:
                print('Yes')
            else:
                print('No')
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# +1/-1の折れ線で表したとき
# 「0で終わる」かつ「途中で0未満にならない」を満たせば良い

# あとは貪欲を上手い事使う


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    b = []
    for _ in range(n):
        s = input().rstrip()
        # 最終的に上がる量/最下点
        up, down = 0, 0
        for i in s:
            if i == ')':
                up -= 1
                if down > up:
                    down = up
            else:
                up += 1
        if up >= 0:
            a.append((down, up))
        else:
            b.append((down-up, -up))

    a.sort(key=lambda a: a[0],reverse=True)
    b.sort(key=lambda a: a[0],reverse=True)

    left, right = 0, 0

    for d, u in a:
        if left+d < 0:
            print('No')
            break
        else:
            left += u
    else:
        for d, u in b:
            if right+d < 0:
                print('No')
                break
            else:
                right += u
        else:
            if left == right:
                print('Yes')
            else:
                print('No')
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# up_list = []
# down_list = []


def count_scan(s):
    max_min = 0
    compare = 0
    for c in s:
        if c == '(':
            compare += 1
        elif c == ')':
            compare -= 1
            max_min = min(max_min, compare)
    return min(max_min, compare), compare


def key(lst):
    m, c = lst
    if c > 0:
        return 1, m
    else:
        return -1, c - m


def main():
    n = int(input())
    lst = [input() for _ in range(n)]

    # up_list.sort(key=lambda x: x[1], reverse=True)
    # down_list.sort(key=lambda x: x[1], reverse=False)
    txt = 'No'
    ans = 0
    # print(lst)
    # print(sorted([count_scan(lst) for i in lst],
                #  reverse=True,
                #  key=key))
    for max_min, c in sorted([count_scan(s) for s in lst],
                             reverse=True,
                             key=key):
        # print(f"{max_min = }, {c = }, {ans = }")
        if max_min + ans < 0:
            break
        ans += c
    else:
        if ans == 0:
            txt = 'Yes'

    print(txt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N = int(input().rstrip('\n'))
S = [str(input().rstrip('\n')) for _ in range(N)]

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    elif now < 0:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1], reverse=True)
minus_stock = sorted(minus_stock, key = lambda x:x[1], reverse=True)

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]
last = now
now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
if last == now:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def count_scan(s):
    max_min = 0
    compare = 0
    for c in s:
        if c == '(':
            compare += 1
        elif c == ')':
            compare -= 1
            max_min = min(max_min, compare)
    return min(max_min, compare), compare
 
 
def key(lst):
    m, c = lst
    if c > 0:
        return 1, m
    else:
        return -1, c - m
 
 
def main():
    n = int(input())
    lst = [input() for _ in range(n)]
 
    txt = 'No'
    ans = 0
    for max_min, c in sorted([count_scan(s) for s in lst],
                             reverse=True,
                             key=key):
        if max_min + ans < 0:
            break
        ans += c
    else:
        if ans == 0:
            txt = 'Yes'
 
    print(txt)
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())


def _kakko(s):
    l, lr = 0, 0
    for c in s:
        if c == ')':
            if lr == 0:
                l = l + 1
            else:
                lr = lr - 1
        else:
            lr = lr + 1
    return (l, lr)


s = [_kakko(input()) for _ in range(n)]

sl = [ss for ss in s if ss[1] >= ss[0]]
sr = [ss for ss in s if ss[1] < ss[0]]

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

r = 0
for ss in sl:
    if ss[0] > r:
        print('No')
        exit(0)
    r = r + ss[1] - ss[0]

for ss in sr:
    if ss[0] > r:
        print('No')
        exit(0)
    r = r + ss[1] - ss[0]

if r != 0:
    print('No')
    exit(0)

print('Yes')

Submission status: Accepted

Solution code:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid-end, -end))

S1.sort(reverse=True)
# S2.sort(key = lambda x : (x[0], -x[1]))
S2.sort(reverse=True)


mid = end1 = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end1 + a
    end1 = end1 + b
    if mid < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break

mid = end2 = 0  # スタート
for t in S2:
    a, b = t
    mid = end2 + a
    end2 = end2 + b
    if mid < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end1 == end2) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid-end, -end))

S1.sort(reverse=True)
# S2.sort(key = lambda x : (x[0], -x[1]))
S2.sort(reverse=True)


mid = end1 = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end1 + a
    end1 = end1 + b
    if mid < 0 or end1 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break

mid = end2 = 0  # スタート
for t in S2:
    a, b = t
    mid = end2 + a
    end2 = end2 + b
    if mid < 0 or end2 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end1 == end2) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
n = int(input())
s = []
for i in range(n):
  s.append(input())

ls = []
rs = []
tot = 0
for si in s:
  b = 0
  h = 0
  for c in si:
    if c == '(':
      h += 1
    else:
      h -= 1
    b = min(h,b)
  if h > 0:
    ls.append((b,h))
  else:
    rs.append((b-h,-h))
  tot += h
ls.sort(reverse = True)
rs.sort(reverse = True)

def check(x):
  t = 0
  for bx,hx in x:
    if t+bx < 0:
      return False
    t += hx
  return True

if check(ls) and check(rs) and tot == 0:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
N, *S = open(0)

L = [s.count("(") for s in S]
R = [s.count(")") for s in S]

X = sorted(((s[:-1], r) for s, l, r in zip(S, L, R) if l - r >= 0), key=lambda x: x[1])
Y = sorted(((s[:-1], l) for s, l, r in zip(S, L, R) if l - r < 0), key=lambda x: -x[1])

cnt = 0
for s, _ in X + Y:
    for si in s:
        cnt += 1 if si == "(" else -1
        if cnt < 0:
            print("No")
            quit()

if cnt == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

xs1total = 0 # ((
xs2 = [] # )((
xs3 = [] # ))(
xs4total = 0 # ))

for s in S:
    n = 0
    m = 0
    for c in s:
        if c == "(":
            n += 1
        elif c == ")":
            n -= 1
            m = min(m, n)
    k = n - m
    if m == 0 and k == 0:
        continue
    elif m == 0:
        xs1total += k
    elif k == 0:
        xs4total += -m
    else:
        if -m < k:
            xs2.append((-m, k))
        else:
            xs3.append((-m, k))

xs2.sort()
xs3.sort(key=lambda x:-(x[1] - x[0]))

def check(xs1total, xs2, xs3, xs4total):
    t = xs1total
    for x in xs2:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    for x in xs3:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    return t == xs4total

#print(xs1total, xs2, xs3, xs4total)

if check(xs1total, xs2, xs3, xs4total):
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

xs1total = 0 # ((
xs2 = [] # )((
xs3 = [] # ))(
xs4total = 0 # ))

for s in S:
    n = 0
    m = 0
    for c in s:
        if c == "(":
            n += 1
        elif c == ")":
            n -= 1
            m = min(m, n)
    k = n - m
    if m == 0 and k == 0:
        continue
    elif m == 0:
        xs1total += k
    elif k == 0:
        xs4total += -m
    else:
        if -m < k:
            xs2.append((-m, k))
        else:
            xs3.append((-m, k))

xs2.sort()
xs3.sort(key=lambda x:-x[1])

def check(xs1total, xs2, xs3, xs4total):
    t = xs1total
    for x in xs2:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    for x in xs3:
        if t < x[0]:
            return False
        t = t - x[0] + x[1]
    return t == xs4total

#print(xs1total, xs2, xs3, xs4total)

if check(xs1total, xs2, xs3, xs4total):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    b=str()
    while a!=b:
        b=a
        a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0 and len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
s=[0]*n
info=[0]*n
for i in range(n):
    ss=list(input())
    now=0
    mi=0
    for sss in ss:
        if sss=="(":
            now+=1
        else:
            now-=1
            mi=min(mi,now)
    info[i]=(mi,now)
#info.sort(key=lambda x:(x[1]>=0)*2+(x[0]>=0),reverse=True )

info0 = []
info1 = []
for i,inf in enumerate(info):
    if inf[1]>=0:
        info0.append(inf)
    else:
        info1.append(inf)
info0.sort(key=lambda x:x[0],reverse=True)
info1.sort(key=lambda x:x[1]-x[0],reverse=True)


ans=True
now=0
for inf in info0:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
for inf in info1:
    if now+inf[0]>=0:
        now+=inf[1]
    else:
        ans=False
if now!=0:
    ans=False
    
print(ans*"Yes"+(1-ans)*"No")

Submission status: Accepted

Solution code:
N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    mi = 0
    now = 0
    for __ in range(len(S)):
        if S[__] == '(':
            now += 1
        else:
            now -= 1
            mi = min(mi, now)
    if now > 0:
        Up.append((mi, now))
    else:
        Down.append((mi - now, mi, now))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for _, i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n = int(input())
l = [0 for i in range(n)]
r = [0 for i in range(n)]


dat = []
dat2 = []
st = -1
for i in range(n):
    s = input()
    for ch in s:
        if ch == '(':
            r[i] += 1
            pass
        else:
            if r[i] > 0:
                r[i] -= 1
            else:
                l[i] += 1
            pass
    # print(i, l[i], r[i])
    if l[i] == 0:
        if st == -1 or r[st] < r[i]:
            st = i
    if r[i] >= l[i]:
        dat.append((l[i], i))
    else:
        dat2.append((r[i], i))

dat.sort()
dat2.sort(reverse=True)


if st == -1:
    print("No")
    exit()

now = r[st]
# print('now={}'.format(now))
for num, i in dat:
    if i == st:
        continue
    if now < l[i]:
        print("No")
        exit()
    now = now - l[i] + r[i]

for num, i in dat2:
    # print('dat2', num, i)
    if now < l[i]:
        print("No")
        exit()
    now = now - l[i] + r[i]
if now == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    on=0
    L=[]
    cn=0#後ろに置くやつ

    for i in range(N):
        s=input()
        close=0
        openn=0
        for ch in s:
            if ch==")":
                if openn==0:
                    close+=1
                else:
                    openn-=1
            else:
                openn+=1
                
                
        if close==0:
            on+=openn
        elif openn==0:
            cn+=close
        else:
            L.append((close-openn,close,-1*openn))
    L.sort()
    flag=1
    
    #print(on)
    
    for co in L:
        cc=co[1]
        oo=co[2]
        #print(cc,oo)
        on-=cc
        if on<0:
            flag=0
            break
        on-=oo
        
    on-=cn   
    
    if on!=0:
        flag=0
        
    if flag==1:
        print("Yes")
    else:
        print("No")
        
        
    
      
        
    

main()

Submission status: Accepted

Solution code:
N = int(input())
pl = []
mi = []

for i in range(N):
    _m = 0
    _t = 0
    s = input()
    for c in s:
        if c == ")":
            _t -= 1
            _m = min(_m, _t)
        else:
            _t += 1
    if _t > 0:
        pl.append([-_m, -_t]) # sortの調整のために負にしている
    else:
        mi.append([- _t + _m,  _m, _t])
pl = sorted(pl)
mi = sorted(mi)

#import IPython;IPython.embed()


if len(pl) == 0:
    if mi[0][0] == 0:
        print("Yes")
    else:
        print("No")
    exit()
if len(mi) == 0:
    print("No")
    exit()

tot = 0
for m, nt in pl:
    if tot - m < 0: # これはひくではないのでは?
        print("No")
        exit()
    else:
        tot -= nt
for d, m, nt in mi:
    if tot + m <0:
        print("No")
        exit()
    else:
        tot += nt
if tot != 0:
    print("No")
else:
    print("Yes")
        



# どういう時できるか
# で並べ方
# tot, minの情報が必要
# totが+のものはminとtotを気をつける必要がある
# minがsum以上であればどんどん足していけばいい.
# なのでminが大きい順にsortし,totの大きい順にsort
# その次はtotがminusの中ではminが小さい順に加える
# 合計が0になる時Yes,それ意外No.

Submission status: Accepted

Solution code:
n = int(input())
li = []

for _ in range(n):
    s = input()
    count = 0
    while True:
        if count + 1 >= len(s):
            break
        if s[count] == '(' and s[count+1] == ')':
            s = s[:count] + s[count+2:]
            count = max(0, count-1)
        else:
            count += 1
    li.append(s)

li2 = []
for i in li:
    count = 0
    for j in range(len(i)):
        if i[j] == ')':
            count += 1
        else:
            break
    li2.append((count, len(i) - count))

li3 = []
li4 = []

for i in li2:
    if i[0] <= i[1]:
        li3.append(i)
    else:
        li4.append(i)

li3.sort()
li4.sort(key = lambda x: x[1], reverse = True)

now = [0,0]

for l,r in li3:
    if l == 0 and r == 0:
        pass
    elif l == 0:
        now[1] += r
    else:
        now[1] -= l
        if now[1] < 0:
            print('No')
            exit()
        now[1] += r

for l,r in li4:
    if l == 0 and r == 0:
        pass
    elif r == 0:
        now[1] -= l
        if now[1] < 0:
            print('No')
            exit()
    else:
        now[1] -= l
        if now[1] < 0:
            print('No')
            exit()
        now[1] += r

if now[0] == 0 and now[1] == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Part:

    def __init__(self, string):
        self.slope, self.floor = self.calc_slope_floor(string)

    def __repr__(self):
        return "s{} f{}".format(self.slope, self.floor)

    def __lt__(self, other):
        if self.floor > other.floor:
            return True
        if self.slope > self.slope:
            return True
        return False

    @staticmethod
    def calc_slope_floor(string):
        slope = 0
        floor = 0
        for c in string:
            if c == '(':
                slope += 1
            else:
                slope -= 1
            floor = min(floor, slope)
        return slope, floor

    def flip(self):
        self.slope *= -1
        self.floor += self.slope

    def catenate(self, other):
        assert(self.slope >= 0)
        if self.slope < abs(other.floor):
            return False
        self.slope += other.slope
        # self.floor is not needed

def sum_slope(parts):
    s = 0
    for p in parts:
        s += p.slope
    return s

def calc_flat_floor(flat):
    floor = 0
    for f in flat:
        floor = min(floor, f.floor)
    return floor

def enable(parts):
    parts = sorted(parts)
    #print('parts') # debug
    #print(parts) # debug
    chain = Part("")
    for p in parts:
        flg = chain.catenate(p)
        if flg == False:
            return False
    return True



def solve(up, down, flat):
    up_slope = sum_slope(up)
    down_slope = sum_slope(down)
    if up_slope != down_slope:
        return False
    flat_floor = calc_flat_floor(flat)
    #print('up_slope') # debug
    #print(up_slope) # debug
    #print('flat_floor') # debug
    #print(flat_floor) # debug
    if up_slope < abs(flat_floor):
        return False
    if not enable(up):
        return False
    if not enable(down):
        return False
    return True


if __name__ == '__main__':
    n = int(input())
    up = []
    down = []
    flat = []
    for _ in range(n):
        s = input()
        p = Part(s)
        if p.slope > 0:
            up.append(p)
        elif p.slope < 0:
            p.flip()
            down.append(p)
        else:
            flat.append(p)
    ans = solve(up, down, flat)
    if ans:
        print("Yes")
    else:
        print("No")


    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
N = int((input()))
C_p = []
C_m = []
for i in range(N):
    kakko = input()
    temp = 0
    temp_min = 0
    for s in kakko:
        if s == "(":
            temp += 1
        else:
            temp -= 1
            temp_min = min(temp, temp_min)
    if temp >= 0:
        C_p.append((temp_min, temp))
    else:
        C_m.append((temp_min - temp, temp_min, temp))
C_p.sort(reverse=True)

flag = 0
final = 0
for l, f in C_p:
    if final + l < 0:
        flag = 1
    final += f

C_m.sort()

for _, l, f in C_m:
    if final + l < 0:
        flag = 1
    final += f
    
if final != 0:
    flag = 1

print("Yes" if flag == 0 else "No")

Submission status: Accepted

Solution code:
def result(m, b):
    sum1 = m
    resmin = m
    for i in range(len(b)):
        resmin += b[i][0]
        if resmin < 0:
            return -1
        else:
            resmin += b[i][1] - b[i][0]
    for i in range(len(b)):
        sum1 += b[i][1]
    if sum1 != 0:
        return -1
    return 0
n = int(input().strip('\n'))
resmin = 10 ** 7
set_pos = []
set_neg = []
for i in range(n):
    a = input().strip('\n')
    loc_min = 10 ** 7
    total = 0
    flag = True
    tmp = 0
    for j in range(len(a)):
        if a[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < loc_min:
            loc_min = tmp
    total = tmp
    if total >= 0:
        set_pos.append((loc_min, total))
    else:
        set_neg.append((loc_min, total))
total_pos = 0
set_pos = sorted(set_pos, key = lambda l: l[0], reverse = True)
for elem in set_pos:
    if total_pos + elem[0] < 0:
        flag = False
    total_pos += elem[1]   
b = sorted(set_neg, key = lambda l: l[1] - l[0], reverse = True)
#print(b)
#print(set_pos, b)
res = result(total_pos, b)
print('No' if (res == -1 or not flag) else 'Yes')

Submission status: Accepted

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

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

ans = 'Yes'
top_plus = 0
for i in range(len(plus)):
    mini, ruikei = plus[i]
    if top_plus + mini < 0:
        ans = 'No'
        break
    else:
        top_plus += ruikei

top_minus = 0
for i in range(len(minus)):
    mini, ruikei = minus[i]
    if top_minus + mini < 0:
        ans = 'No'
        break
    else:
        top_minus += ruikei

if top_plus != top_minus:
    ans = 'No'

print(ans)