AtCoder ABC 167 F Bracket Sequencing

ABC 167は5完 Eの実装で時間を溶かしてしまってFが解けなかった。

atcoder.jp

問題としては( と )だけの文字列が複数与えられるので、好きな順番で連結して、括弧の対応が取れた文字列にできるかどうかの判定

それぞれの文字に対し対応する括弧を潰すと、))(((のような形になるので、)の数をr, (の数をlとして、(r, l)で考える。
先頭にできるのはr = 0だけ、末尾にできるのはl = 0だけ、それ以外は中間部

カッコ列は(の数が先行して、)が追い付く形になるので、i個連結して括弧の対応が取れた状態にするには 、ただしを満たす順番で、 且つ である必要がある。
先頭部、中間部(r - lで昇順にソート)、後尾部を順次連結して、全部追加できるか + 括弧の数が同じかを確認して終了。

中間部(r - lで昇順にソート)で貪欲にやって通ったけど不安。解説見るとr - l <= 0, r - l > 0に分けてr 昇順, l降順で足していくとよいらしい。なるほどなー。

N = gets.to_i
S = []
T = []
W = []
 
N.times do
  w = gets.chomp
  r = 0; l = 0; 
  (0 ... w.size).each do |i|
    c = w[i]
    if c == '('
      l += 1
    elsif l > 0
      l -= 1
    else
      r += 1
    end
  end
  if l.zero? # terminate
    T << [r, l]
  elsif r.zero?
    S << [r, l] # start
  else
    W << [r, l]
  end
end
 
l_sum = S.inject(0){|s,(r,l)| s + l }
 
W.sort_by!{|r,l| r - l }
W.each do |(r,l)|
  if l_sum >= r
    l_sum = l_sum - r + l
  else
    puts 'No' 
    exit
  end
end
 
T.each do |(r,l)|
  if l_sum >= r
    l_sum = l_sum - r + l
  else
    puts 'No' 
    exit
  end
end
 
puts l_sum.zero? ? 'Yes' : 'No'

atcoder.jp