square869120Contest #5：C - Two Parentheses
問題
解法
A, B の "(" , ")" の数がそれぞれ |S| / 4 になっていればよい．S を先頭から見ていくとき，S を真ん中で半分にして考える．
前半分のとき，
- S_i == "(" で A の "(" が不足しているとき：A += "("
- S_i == "(" で A の "(" が不足していないとき：B += "("
- S_i == ")" で B の ")" が不足しているとき：B += ")"
- S_i == ")" で B の ")" が不足していないとき：A += ")"
A の "(" が不足していないときに A += "(" する，または，B の ")" が不足していないときに B += ")" すると A, B は「正しい括弧列」ではなくなる．なので，前者なら B += "("，後者なら A += ")" することによって回避できる．
後半分の時
- S_i == "(" で A の "(" が不足しているとき：A += "("
- S_i == "(" で B の "(" が不足しているとき：B += "("
- S_i == "(" でどちらも "(" が不足していないとき：終了
- S_i == ")" で B の ")" が不足しているとき：B += ")"
- S_i == ")" で A の ")" が不足しているとき：B += ")"
- S_i == ")" でどちらも ")" が不足していないとき：終了
前半分と同様の理由でこのような処理になる．どちらも不足していないのにまだ括弧があるときは， "(" または ")" の個数がそもそも正しくないので「正しい括弧列」は作れない．
このように貪欲をして，B の括弧を反転させて，A, B 両方が「正しい括弧列」であれば "Yes"，そうでなければ "No" を出力すればよい．O(Q|S|)．
解答
最初は怪しかった貪欲が意外と通ってしまった．
