SRM480 Easy:InternetSecurity
keyword
概要
サイトのアドレス名、各サイトが含んでいるキーワード、危険ワード、閾値が与えられる。閾値以上の危険ワードを含むサイトは危険であると判断され、そのサイトが含むキーワードは危険ワードに追加される。危険なサイトのアドレスを返す問題。
危険ワードが途中で増えるので何度もループを回す必要がある。ループ回数はアップデートするかどうかのフラグで管理してもよいし、サイトの数だけ回してもよい。
vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) { set<string> dang; int i, j, loop, n=SZ(address); string str; vector<bool> isDang(n,false); vector<string> ret; vector<vector<string> > keys(n); REP(i,n){ istringstream ist(keyword[i]); while(ist>>str){ keys[i].PB(str); } } REP(i,SZ(dangerous)) dang.insert(dangerous[i]); REP(loop,51){ REP(i,n)if(!isDang[i]){ int cnt = 0; REP(j,SZ(keys[i])){ if(dang.find(keys[i][j])!=dang.end()){ cnt++; } } if(cnt>=threshold){ isDang[i] = true; REP(j,SZ(keys[i])){ dang.insert(keys[i][j]); } } } } REP(i,n)if(isDang[i])ret.PB(address[i]); return ret; }