TCO2012 Round1A Easy(250) EllysJuice

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());
}};