ABC167 F - Bracket Sequencing (600)
本番中の考察
それぞれの文字列の()の合計が同じになってなかったら不可能
それぞれの文字列中で最大でどれだけ事前に(が必要かと、最終的なその文字列での()の収支を記録
事前の必要数と収支が同じで最後が)で終わる文字列の内一つを最後に使う文字列と決めておいて除外
事前の必要数の少ない順にソート
現在の収支の状態で使える文字列を優先度付きキューに可能な限り追加
キューの内収支が良い順にどんどん使っていく
最後まで使えたらOK、途中で詰まったら駄目
収支が負の場合は上の方法だとWA
解説の方法
収支が正と負の二つに分ける
正の方は必要数が小さい順に使って行く
どんどんと収支が良くなるので条件が緩和されていく
全部使えない場合は駄目
負の場合も左右反転すると正と同じように考えられる
収支は反転
必要数は収支の分だけ改善
あとは正の場合と同じに考えることができる
優先度付きキューへの追加・削除がボトルネックで$ O(N \log N)