SRM 327 DIV1 Easy - NiceOrUgly (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=6871&rd=10007
・？を含んだ文字列が与えられる。
・母音が３つ連続する、または子音が５つ連続したらその文字列はＵＧＬYであり、そうでなければＮＩＣＥである。
・？は任意の文字に置き換えられる。
このとき、与えられた文字列がＮＩＣＥであればＮＩＣＥを返し、ＵＧＬＹであればＵＧＬＹ，どちらもあり得るのであれば４２を返す。
解き方
文字の長さが最大５０であることから全探索はできない。
ここでｄｐを考えると、状態の数はdp[50][3][5]であるためdpで解くことができる。
コード
int dp[100][100][100];
string str;
class NiceOrUgly {
public:
bool is_vow(char ch){
return ch=='A'||ch=='E'||ch=='I'||ch=='O'||ch=='U';
}
int calc(int pos,int x,int y){
if(x>=3||y>=5)return 2;
if(pos>=str.size())return 1;
if(dp[pos][x][y]!=-1)return dp[pos][x][y];
int ret=0;
if(str[pos]=='?'){
ret|=calc(pos+1,x+1,0);
ret|=calc(pos+1,0,y+1);
}
else{
if(is_vow(str[pos]))ret|=calc(pos+1,x+1,0);
else ret|=calc(pos+1,0,y+1);
}
return dp[pos][x][y]=ret;
}
string describe(string s) {
memset(dp,-1,sizeof(dp));
str=s;
int ret=calc(0,0,0);
if(ret==3)return "42";
if(ret==1)return "NICE";
return "UGLY";
}
};
string str;
class NiceOrUgly {
public:
bool is_vow(char ch){
return ch=='A'||ch=='E'||ch=='I'||ch=='O'||ch=='U';
}
int calc(int pos,int x,int y){
if(x>=3||y>=5)return 2;
if(pos>=str.size())return 1;
if(dp[pos][x][y]!=-1)return dp[pos][x][y];
int ret=0;
if(str[pos]=='?'){
ret|=calc(pos+1,x+1,0);
ret|=calc(pos+1,0,y+1);
}
else{
if(is_vow(str[pos]))ret|=calc(pos+1,x+1,0);
else ret|=calc(pos+1,0,y+1);
}
return dp[pos][x][y]=ret;
}
string describe(string s) {
memset(dp,-1,sizeof(dp));
str=s;
int ret=calc(0,0,0);
if(ret==3)return "42";
if(ret==1)return "NICE";
return "UGLY";
}
};
