kmjp's blog

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

TopCoder SRM 666 Div2 Medium GoodString

Div2 Mediumにしては簡単だけど、444ptということで450pt相当?
http://community.topcoder.com/stat?c=problem_statement&pm=13751

問題

空文字列から初めて、文字列のどこかに"ab"を追加する、という処理を何度か行ってできる文字列はGoodであるとする。
L文字の文字列Sが与えられるので、それがGoodかどうか判定せよ。

解法

「"ab"の並びを取り除く」という処理を可能な限り繰り返せばよく、O(N^2)で終わる。

また"a"→"["、"b"→"]"と置き換えて考えると、これは文字列がcorrect bracket sequenceか聞かれているのと等しい。
よって、文字を頭から見ていて「常に登場した閉じ括弧の数は開き括弧の数以下である」「閉じ括弧と開き括弧の数は等しい」だけを判定すればO(N)で解ける。

class GoodString {
	public:
	string isGood(string s) {
		int numa=0;
		FORR(r,s) {
			if(r=='a') numa++;
			else {
				numa--;
				if(numa<0) return "Bad";
			}
		}
		if(numa==0) return "Good";
		return "Bad";
	}
}

まとめ

"ab"よりもっと"良い"文字ないかなと思ったけど思い浮かばなかった。
4と7とか?