TopCoder SRM 670 Div2 Medium Drbalance

変な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=14060

問題

• • で構成された文字列のバランスとは、文字列中における( (+の数)-(-の数) )で計算できる。

文字列Sが与えられる。
Sのprefixのうち、バランスが負になるものをK個以下にしたい。
文字列Sの中身を+-反転できるとき、条件を満たすのに必要な最小反転数を求めよ。

解法

反転させるなら、先頭に近い方の-を+にする方がより多くのprefixがバランス負になることを防止できる。
よって「全prefixのうちバランスが負のものがK個以下かチェック」→「そうでないなら、先頭に近い-を+に反転」を繰り返せばよい。

class Drbalance {
	public:
	int lesscng(string s, int k) {
		int cnt=0;
		while(1) {
			int neg=0;
			int cur=0;
			FORR(r,s) {
				if(r=='+') cur++;
				else cur--;
				if(cur<0) neg++;
			}
			if(neg<=k) return cnt;
			cnt++;
			FORR(r,s) if(r=='-') {
				r='+';
				break;
			}
		}
	}
}

まとめ

なんとなくcorrect bracket sequenceを意識した問題？