kmjp's blog

競技プログラミング参加記です

TopCoder SRM 715 Div1 Easy MaximumRange、Div2 Medium MaximumRangeDiv2

EasyもMediumも通せたので本番出ておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14613
https://community.topcoder.com/stat?c=problem_statement&pm=14611

問題

"+-"の文字列がある。
初期値0に変数し、各文字に対応して数値をインクリメント・デクリメントすることを考える。
文字列の部分列に対し、変数の最大値・最小値の差が最大となるようにしたい。
あり得る差の最大値を求めよ。

解法

全部+か全部-にすればよいので、結局+-の数の多い方を答えればよい。

class MaximumRange {
	public:
	int findMax(string s) {
		int np=0;
		int nm=0;
		FORR(c,s) {
			if(c=='-') nm++;
			if(c=='+') np++;
		}
		return max(nm,np);
		
	}
}

まとめ

これDiv2 Easyクラスの気がするんだけど…。