SRM 480 250pt: InternetSecurity

問題概要

サイト名がN(<50)個あり、各サイトはキーワードをいくつか持っている。最初に、危険なキーワードがいくつか与えられる。危険なキーワードを閾値以上含むサイトは危険であると判定され、そのサイトに含まれる全てのキーワードは危険なキーワードに追加される。危険なサイトを全て答える問題。

考えたこと

• (本番もひたすらアルゴリズムをシミュレートして通した記憶がある)
• 与えられたアルゴリズムを愚直に適用してアップデートがなくなるまで繰り返す。

practiceで通ったコード

#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;


struct InternetSecurity {

	vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
		const int N = address.size();
		set<string> dangerous_word(dangerous.begin(), dangerous.end());
		vector< vector<string> > words(N);
		vector<bool> is_dangerous(N, false);

		for(int i=0; i<N; i++){
			stringstream ss(keyword[i]);
			string str;
			while(ss>>str){
				words[i].push_back(str);
			}
		}

		for(;;){
			bool update = false;

			for(int i=0; i<N; i++)if(!is_dangerous[i]){
				int cnt = 0;
				for(int j=0; j<(int)words[i].size(); j++){
					if(dangerous_word.find(words[i][j]) != dangerous_word.end()){
						cnt++;
					}
				}

				if(cnt >= threshold){
					dangerous_word.insert(words[i].begin(), words[i].end());
					is_dangerous[i] = true;
					update = true;
				}
			}

			if(!update){
				break;
			}
		}

		vector<string> ret;
		for(int i=0; i<N; i++)if(is_dangerous[i]){
			ret.push_back(address[i]);
		}

		return ret;
	}

};