問題
http://community.topcoder.com/stat?c=problem_statement&pm=6871&rd=10007
・?を含んだ文字列が与えられる。
・母音が3つ連続する、または子音が5つ連続したらその文字列はUGLYであり、そうでなければNICEである。
・?は任意の文字に置き換えられる。
このとき、与えられた文字列がNICEであればNICEを返し、UGLYであればUGLY,どちらもあり得るのであれば42を返す。
解き方
文字の長さが最大50であることから全探索はできない。
ここでdpを考えると、状態の数は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";
}
};