問題
http://community.topcoder.com/stat?c=problem_statement&pm=10696&rd=14144
”17:45 GMT-4”と時刻を表す時計がある。
ただし時計の一部が壊れており、その箇所は？になっている。
このとき、考えられる昇順で一番早い時間を求める。
解き方
法則を考えると大変なため、全探索を用いる必要があるのがわかる。
ここでのコツは、すべての数字を前端さ区しようとするのではなくて
すべての文字列を発生させて全探索する。
コード
string ret;
class TheTriangleBothDivs {
public:
void rec(string time, int pos){
if(pos>=time.size()){
int h=(time[0]-'0')*10+(time[1]-'0');
int m=(time[3]-'0')*10+(time[4]-'0');
int d=time[10]-'0';
if(time[9]=='-' && d==0)return;
if(h>=24 || m>=60)return;
if(time[9]=='-')d=-d;
char ch[50];
sprintf(ch,"%02d:%02d",((h-d)+24)%24,m);
if(ch<ret)ret=ch;
}else if(time[pos]=='?'){
string str="0123456789";
if(pos==9)str="-+";
FORE(i,0,str.size()){
time[pos]=str[i];
rec(time,pos+1);
time[pos]='?';
}
}else rec(time,pos+1);
}
string fix(string time) {
ret="99:99";
rec(time,0);
return ret;
}
};
class TheTriangleBothDivs {
public:
void rec(string time, int pos){
if(pos>=time.size()){
int h=(time[0]-'0')*10+(time[1]-'0');
int m=(time[3]-'0')*10+(time[4]-'0');
int d=time[10]-'0';
if(time[9]=='-' && d==0)return;
if(h>=24 || m>=60)return;
if(time[9]=='-')d=-d;
char ch[50];
sprintf(ch,"%02d:%02d",((h-d)+24)%24,m);
if(ch<ret)ret=ch;
}else if(time[pos]=='?'){
string str="0123456789";
if(pos==9)str="-+";
FORE(i,0,str.size()){
time[pos]=str[i];
rec(time,pos+1);
time[pos]='?';
}
}else rec(time,pos+1);
}
string fix(string time) {
ret="99:99";
rec(time,0);
return ret;
}
};