SRM 327 Div1 Easy / Div 2 Hard NiceOrUgly

問題

アルファベットもしくは'?'からなる文字列が与えられる。
母音字が3つ以上連続で、もしくは子音字が5つ以上連続で並ぶ、のどちらかの条件を満たすような文字列をUGLYであるという。そうでない文字列をNICEであるという。

'?'にどのような文字を入れても文字列がUGLYになるならUGLYを、どのような文字を入れてもNICEになるならNICEを、どちらにもできるなら42を返せ。

制約条件

文字列の長さ≦50

方針

探索するのか？とか思ったらDPでいけるらしい。
TopCoderの探索は大抵DPに落とせる←教訓

文字列をuglyにできるかどうかは簡単に判定できる。
niceにできるかは、dp[i][j][k]に、i文字までで、母音字がj文字連続していて、子音字がk文字連続している（今のところniceな）文字列があるかどうかをもっておき、更新してくようなdpによりできる。
dp[n][i][j]で1になるようなものがあればniceにできるという訳。

ソースコード

int n,dp[51][3][5];
bool vow(char c){
	return c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
}

class NiceOrUgly {
	public:
	string describe(string s) 
	{
		n=s.size();
		bool ugly=0,nice=0;
		rep(i,n-2){
			bool ok=1;
			rep(j,3)if(s[i+j]!='?'&&!vow(s[i+j]))ok=0;
			ugly|=ok;
		}
		rep(i,n-4){
			bool ok=1;
			rep(j,5)if(vow(s[i+j]))ok=0;
			ugly|=ok;
		}
		
		rep(i,n+1)rep(j,3)rep(k,5)dp[i][j][k]=0;
		dp[0][0][0]=1;
		rep(i,n)rep(j,3)rep(k,5)if(dp[i][j][k]){
			if(j<2&&(s[i]=='?'||vow(s[i])))dp[i+1][j+1][0]=1;
			if(k<4&&(!vow(s[i])))dp[i+1][0][k+1]=1;
		}
		rep(j,3)rep(k,5)nice|=dp[n][j][k];
		
		if(!ugly)return "NICE";
		return nice?"42":"UGLY";
	}
};