問題
http://community.topcoder.com/stat?c=problem_statement&pm=11064&rd=14159
N個のWebサイトがあり、その危険性を検証したい。
各Webサイトについて、サイトのアドレスと関連するキーワードが
わかっている。
また、危険なキーワードが複数与えられ、あるWebサイト中に
危険なキーワードがthreshold以上存在するとそのWebサイトは危険になる。
また、Webサイトが危険になると、そのサイトに関連する
すべてのキーワードも危険になる。
このとき、危険なWebサイトのアドレスすべてを昇順に並べたものを求める。
解き方
実装問題なので、正確にかつシンプルなデータ構造で実装するだけ。
コード
class InternetSecurity {
public: vector<string> determineWebsite(vector<string> address, vector<string> keyword, vector<string> dangerous, int threshold) {
int n=address.size();
int p[n];
memset(p,-1,sizeof(p));
set<string> d;
FORE(i,0,dangerous.size())d.insert(dangerous[i]);
string key[51][51];
FORE(i,0,51)FORE(j,0,51)key[i][j]="";
FORE(i,0,n){
stringstream out(keyword[i]);
int at=0;
while(out>>key[i][at++]);
}
int next=1;
while(next){
next=0;
FORE(i,0,n){
int cnt=0,at=0;
while(!key[i][at].empty()){
if(d.find(key[i][at])!=d.end())cnt++;
at++;
}
if(p[i]==-1 && cnt>=threshold){
p[i]=cnt;
next=1;
int att=0;
while(!key[i][att].empty()){
d.insert(key[i][att++]);
}
}
}
}
vector<string> ans;
FORE(i,0,n)if(p[i]>=threshold)ans.push_back(address[i]);
return ans;
}
};
public: vector<string> determineWebsite(vector<string> address, vector<string> keyword, vector<string> dangerous, int threshold) {
int n=address.size();
int p[n];
memset(p,-1,sizeof(p));
set<string> d;
FORE(i,0,dangerous.size())d.insert(dangerous[i]);
string key[51][51];
FORE(i,0,51)FORE(j,0,51)key[i][j]="";
FORE(i,0,n){
stringstream out(keyword[i]);
int at=0;
while(out>>key[i][at++]);
}
int next=1;
while(next){
next=0;
FORE(i,0,n){
int cnt=0,at=0;
while(!key[i][at].empty()){
if(d.find(key[i][at])!=d.end())cnt++;
at++;
}
if(p[i]==-1 && cnt>=threshold){
p[i]=cnt;
next=1;
int att=0;
while(!key[i][att].empty()){
d.insert(key[i][att++]);
}
}
}
}
vector<string> ans;
FORE(i,0,n)if(p[i]>=threshold)ans.push_back(address[i]);
return ans;
}
};