kmjp's blog

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

TopCoder SRM 593 Div2 Medium WolfDelaymaster

今回のDiv2 MediumはDiv1 Hardを簡単にした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12778

問題

w,o,l,fの4文字から構成される文字列がある。
これらが、wolfを整数倍に拡大した文字(たとえばwwwooolllfff)を連結した文字かどうか答えよ。

解法

文字列を1文字目から見ていく。
今見ている文字がwでなければ、題意を満たさない。
今見ている文字がwである場合、wが何文字続くか数えることで、想定される倍率Mがわかるので続く4×M文字がwolfをM倍したものか判定すればよい。

class WolfDelaymaster {
	public:
	string check(string str) {
		int i;
		for(int pos=0;pos<str.size();) {
			int num=0;
			while(str[pos]=='w' && pos<str.size()) num++,pos++;
			if(num==0) return "INVALID";
			FOR(i,num) if(pos>=str.size() || str[pos]!='o') return "INVALID"; else pos++;
			FOR(i,num) if(pos>=str.size() || str[pos]!='l') return "INVALID"; else pos++;
			FOR(i,num) if(pos>=str.size() || str[pos]!='f') return "INVALID"; else pos++;
		}
		return "VALID";
	}
}

まとめ

Div2 Medium==Div1 Easyと考えると今回はえらく簡単だな。

広告を非表示にする