kmjp's blog

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

TopCoder SRM 609 Div1 Easy MagicalStringDiv1

SRM609は出られない予定だったが、急遽出られることに。
今回はEasy・Mediumがえらく簡単だった回。225pt/450ptでもいいんじゃないかというぐらい。
自分はEasyはサクサク解けたけどMediumでちょっと手こずった。
ともあれEasy/Mediumを解けてレートが微増。
http://community.topcoder.com/stat?c=problem_statement&pm=13003

問題

'>' '<' だけで構成された文字列がある。
ここからいくつかの文字を取り除き、'>'がいくつか連続した後に同数の'<'が来るようにしたい。
条件を満たす最長の文字列長を求めよ。

解法

いろんなやり方がある。
自分は、文字列を前から見て途中まで'>'を拾い、残りは'<'を拾うようにして少ない方に数を合わせる、という手法で対応。
'>'を拾い終える位置を総当たりで変えることでO(L^2)で解答。

class MagicalStringDiv1 {
	int L;
	public:
	int getLongest(string S) {
		int i,x,r=0;
		L=S.size();
		for(i=-1;i<L+3;i++) {
			int a=0,b=0;
			FOR(x,L) {
				if(x<i && S[x]=='>') a++;
				if(x>=i && S[x]=='<') b++;
			}
			r=max(r,2*min(a,b));
		}
		return r;
	}
};

まとめ

これはDiv2 Easyか225ptでいいのでは…。

広告を非表示にする