AtCoder ABC #167 : F - Bracket Sequencing

ミス多すぎ。
https://atcoder.jp/contests/abc167/tasks/abc167_f

問題

N通りのカッコ列が与えられる。
これらを任意の並び順で連結したとき、全体が整合性のとれたカッコ列にできるか判定せよ。

解法

まず、定番の方法として各カッコ列を以下のように言い換える。
'(',')'を変数vのインクリメント・デクリメントに対応付けたとき、初期値v=0から初めて文字を順に読んだとき、vの最小値mとv最終値fからなるタプル(m,f)とする。
変数vにタプル(m,f)を適用できるのはv≧mの時であり、その時v=v+fに遷移すると考える。(vは要は余分な開きカッコの数に相当する)

変数v=0に、このタプルを順に適用したとき、途中vが負になることなく、最後v=0になるような適用順を考えよう。
その際、タプルをf≧0のものとf＜0のものに分けて考えよう。

f≧0のタプルは、mが大きい順にどん欲に適用していけばよい。
タプルを適用すれば適用するほどvの値は大きくなるので、条件の緩い順に行えばよいことになる。

次にf＜0のケースだが、これは文字列を反転して逆順から読んだ場合を考えてみる。
文字列を反転すると、タプル(m,f)は(m-f,-f)になる。
このタプルについて、上記同様にどん欲に変数w=0に適用してみる。
結果、両者全タプルを条件を満たして適用しつつ、v=wならよい。

int N;
multiset<pair<int,int>> add,del;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		int cur=0,mi=0;
		FORR(c,s) {
			if(c=='(') cur++;
			else cur--;
			mi=min(mi,cur);
		}
		
		if(cur>=0) add.insert({-mi,cur});
		if(cur<0) del.insert({-(mi-cur),-cur});
	}
	
	int cur=0;
	FORR(a,add) {
		if(cur-a.first<0) return _P("No\n");
		cur+=a.second;
	}
	x=cur;
	
	cur=0;
	FORR(a,del) {
		if(cur-a.first<0) return _P("No\n");
		cur+=a.second;
	}
	if(x==cur) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
}

まとめ

multisetのソート順を逆順に勘違いしてWAした。
なぜサンプルが通ったのだ…。