ABC167-F Bracket Sequencing
ARMERIAさんのブログが非常にわかりやすかった
問題
解法
'(':+1
')':-1
と対応させると，適当に文字列を構成した時に累積和Sが以下を満たすようなパターンは存在するか？という問題に言い換えられる．
1.任意のindexに対してS[index]>=0
2.最終的な全体の累積和S[end]==0
すると，2については全体の文字列パターンが与えられたときに満たすかどうかは明らかなのでどうでもよくて，1が常に満たされるように上手いこと帳尻合わせをする必要がある．
ここで，1の条件を言い換えると，以下のように言える．
その文字列の累積和のmin>=0
また，この問題はパーツをうまい具合に組み合わせるという形式なので，もっと細かく言えば以下が言える．
ある文字列パーツを組み合わせたところまでの文字列に対してさらに新たな文字列パーツを組み合わせる．その新しい文字列パーツの区間に対応する累積和のmin>=0(★）
するとそのある文字列パーツまでの累積和を考えたときに，新しく文字列パーツを組み合わせたときの累積和のminとなるのはどういう部分かというと，その新たに付け加える文字列パーツ自身の累積和のminに対応する部分に対応するはずである．
よって文字列パーツは以下の成分によって特徴づけることができる．
1.その文字列パーツ内の累積和の最小値mn
2.その文字列パーツを最後まで辿ったときの累積和sm
あとはどういう順序で付け加えていくかというところだが，初期の累積和を0とした時に，（★）の部分から，mnはなるべく大きいものから取っていったほうが良さそうである．また，最終的にできる文字列パターンを考えると，前半は'('が多いほうが良さそうである．このことから，前半部分についてはsm>=0なるところからmnが大きいものを順に選んで組み合わせれば良さそうである．
問題は後半部分で，前半でsm>=0なるところから選んでいるので後半の方は必然的にその部分までの貯金を崩していく（＝sm<0の文字列パーツ郡から選んでいく）ことになるのだが，単純にmnが大きいものから順に選んでしまうと，mnが非常に小さいものが来た時に累積和が足りなくて構成できない場合が考えられる．よって，もし使えるなら余裕があるうちにmnが小さいものを使いたい．一方で，単純にmnが小さい順に選ぶとその文字列を組み合わせた後の累積和が小さくなりすぎて構成に失敗してしまうことが考えられる．よってsmはできるだけ大きいものを選びたい．
このことを考えるとsm-mnが大きい順に選んでいけば良さそうである．（正当性はARMERIAさんのブログを参照）
あとはこれを実装すれば良い．
