SRM480 Div1 Easy(250), Div2 Medium(500) InternetSecurity
アルゴリズムが書かれているので、その通りに実装する。
#include <vector> #include <string> #include <set> #include <sstream> using namespace std; class InternetSecurity{public: vector <string> determineWebsite( vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold ) { int N = (int)address.size(); vector<vector<string> > word( N ); for ( int i=0; i<N; i++ ) { stringstream ss( keyword[i] ); string t; while ( ss >> t ) word[i].push_back( t ); } set<string> danger( dangerous.begin(), dangerous.end() ); vector<bool> site( N, false ); bool up; do { up = false; for ( int i=0; i<N; i++ ) if ( ! site[i] ) { int c = 0; for ( vector<string>::iterator w=word[i].begin(); w!=word[i].end(); w++ ) if ( danger.count( *w ) > 0 ) c++; if ( c >= threshold ) { site[i] = true; for ( vector<string>::iterator w=word[i].begin(); w!=word[i].end(); w++ ) danger.insert( *w ); up = true; } } } while ( up ); vector<string> answer; for ( int i=0; i<N; i++ ) if ( site[i] ) answer.push_back( address[i] ); return answer; } };