TCO2012 Round1A Easy(250) EllysJuice
プレイヤーの人数が高々8人なので、全ての並びを試せば良い。実装がけっこう面倒くさい。
#include <string> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; class EllysJuice{public: vector <string> getWinners( vector <string> players ) { int n = (int)players.size(); set<string> ans; sort(players.begin(),players.end()); do { int J[2] = { 1024, 1024 }; // 残っているジュース map<string,int> D; // 飲んだジュース for ( int i=0; i<n; i++ ) D[players[i]] += J[i%2]/2, J[i%2] /= 2; int td = 0; string tn; bool f = false; for ( map<string,int>::iterator it=D.begin(); it!=D.end(); it++ ) { if ( it->second == td ) f = false; if ( it->second > td ) td = it->second, tn = it->first, f = true; } if ( f ) ans.insert(tn); } while ( next_permutation(players.begin(),players.end()) ); return vector<string>(ans.begin(),ans.end()); }};