yukicoder : No.684 Prefix Parenthesis

時間通り参加できないわ集中できる環境に無いわで散々。
https://yukicoder.me/problems/no/684

問題

開き括弧閉じ括弧のみで構成される、N文字の文字列Sが与えられる。

S(i)をSのi文字のprefixとする。
S(1)～S(N)を任意に並べ替えたとき、その部分列のうちcorrect parenthesis sequenceの最長の長さを求めよ。

解法

prefixを考える際、その中で開き括弧閉じ括弧の対応が取れている部分に関しては、S(i)の並べ方を問わず対応が取れるのでその分解の長さに含める。
対応のとれた文字を除くと、S(i)に残される文字列は閉じ括弧いくつかのあと開き括弧いくつかとなる。

後は良くあるこの２値を元にして比較関数を用いてソートする手法である。
閉じ括弧が先行する数が多いほどcorrect parenthesis sequenceに残る文字数が減るので、閉じ括弧が先行する数が少なくなるようにソートしよう。

int N;
string S;
int A[101010],B[101010],C[101010];
ll ret;
vector<pair<ll,ll>> V;

bool cmp(pair<ll,ll> L,pair<ll,ll> R) {
	return minmax(-L.first,-L.first+L.second-R.first) > minmax(-R.first,-R.first+R.second-L.first);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		A[i+1]=A[i];
		B[i+1]=B[i];
		C[i+1]=C[i];
		if(S[i]=='(') {
			B[i+1]++;
		}
		else {
			if(B[i+1]) {
				B[i+1]--;
				C[i+1]++;
			}
			else {
				A[i+1]++;
			}
		}
		ret+=C[i+1];
		V.push_back({A[i+1],B[i+1]});
	}
	
	sort(ALL(V),cmp);
	ll cur=0;
	FORR(v,V) {
		//cout<<v.first<<" "<<v.second<<" "<<cur<<" "<<ret<<endl;
		ret+=min(cur,v.first);
		cur-=min(cur,v.first);
		cur+=v.second;
	}
	cout<<ret*2<<endl;
	
}

まとめ

近いところまでは行ったけど時間内には間に合わなかった。