問題
http://community.topcoder.com/stat?c=problem_statement&pm=11359&rd=14431
解き方
初期配列のままで各文字列ペアについて包含しているかで判定すると
３つ以上の要素が互いに関係する場合にただしく計算できない。
そのため、ある文字列に包含できる場合はその文字列を削除することで
排他的に答えを求める。
コード
class TheLotteryBothDivs {
public:
bool issuffix(string s1,string s2){
int n=min(s1.size(),s2.size());
FORE(i,0,n)if(s1[s1.size()-1-i]!=s2[s2.size()-1-i])return false;
return true;
}
double find(vector<string> g) {
while(1){
next:
FORE(i,0,g.size())FORE(j,i+1,g.size()){
if(issuffix(g[i],g[j])){
if(g[i].size()<g[j].size())swap(g[i],g[j]);
vector<string>::iterator it=g.begin();
g.erase(it+i);
goto next;;
}
}
break;
}
double ret=0;
FORE(i,0,g.size())ret+=pow(0.1,g[i].size());
return ret;
}
};
public:
bool issuffix(string s1,string s2){
int n=min(s1.size(),s2.size());
FORE(i,0,n)if(s1[s1.size()-1-i]!=s2[s2.size()-1-i])return false;
return true;
}
double find(vector<string> g) {
while(1){
next:
FORE(i,0,g.size())FORE(j,i+1,g.size()){
if(issuffix(g[i],g[j])){
if(g[i].size()<g[j].size())swap(g[i],g[j]);
vector<string>::iterator it=g.begin();
g.erase(it+i);
goto next;;
}
}
break;
}
double ret=0;
FORE(i,0,g.size())ret+=pow(0.1,g[i].size());
return ret;
}
};