SRM422 div2 hard
どの人が食べられるケーキにするかをビットで管理して全探索する。
#include <algorithm> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; class BirthdayCake { public: set<string> fruit; int s2i(string s) { return (int)distance(fruit.begin(),fruit.find(s)); } int popCount(int n) { int r=0; for(int i=0;i<25;i++) if(n & (1<<i)) r++; return r; } int howManyFriends(vector <string> availableFruits, vector <string> friendsDislikings, int K) { int nFriend=friendsDislikings.size(); for(int i=0;i<(int)availableFruits.size();i++) fruit.insert(availableFruits[i]); for(int i=0;i<nFriend;i++) { string s; stringstream ss(friendsDislikings[i]); while(ss >> s) fruit.insert(s); } int nFruit=fruit.size(); vector<int> useFruit(nFruit,0); for(int i=0;i<(int)availableFruits.size();i++) useFruit[s2i(availableFruits[i])]=1; vector<vector<int> > fD(nFriend); for(int i=0;i<nFriend;i++) { string s; stringstream ss(friendsDislikings[i]); while(ss >> s) fD[i].push_back(s2i(s)); } int ans=0; int a=0; for(int i=0;i<nFruit;i++) a+=useFruit[i]; //printf("nFriend=%d nFruit=%d\n",nFriend,nFruit); for(int eat=0;eat<(1<<nFriend);eat++) { //printf("eat=%d\n",eat); int r=a; vector<int> v=useFruit; for(int i=0;i<nFriend;i++) if(eat & (1<<i)) { //printf("%d ",i); for(int j=0;j<fD[i].size();j++) if(v[fD[i][j]]==1) { r--; v[fD[i][j]]=0; //if(r<K) // goto B1; } } //B1: //printf("\n"); //printf("r=%d\n\n",r); if(K<=r) ans=max(ans,popCount(eat)); } return ans; } };