kmjp's blog

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

TopCoder SRM 618 Div2 Medium LongWordsDiv2

Div2 MediumはDiv1 Mediumを簡単にしたもの。
http://community.topcoder.com/stat?c=problem_statement&pm=13147

問題

以下の文字列は好ましい文字列とする。

  1. アルファベット大文字だけで構成される
  2. 同じ文字が連続しない
  3. ある2種類の文字x,yに対して、部分文字列としてxyxyを持たない

文字列が与えられるので好ましい文字列かどうか答えよ。

解法

入力文字列自体大文字だけで構成されているので、上記条件2,3をチェックすればよい。
文字列長N<=100なので、条件3は文字を4つ総当たりでチェックしてO(N^4)かけても間に合う。

class LongWordsDiv2 {
	public:
	string find(string word) {
		int N=word.size(),x1,x2,y1,y2;
		int i;
		FOR(i,N-1) if(word[i]==word[i+1]) return "Dislikes";
		FOR(x1,N) for(y1=x1+1;y1<N;y1++) for(x2=y1+1;x2<N;x2++) for(y2=x2+1;y2<N;y2++) {
			if(word[x1]==word[x2] && word[y1]==word[y2]) return "Dislikes";
		}
		return "Likes";
	}
};

まとめ

これはDiv2 Mediumにしても簡単な気がする。
単純な総当たりでいいしね。

広告を非表示にする