2012 TCO Round 1A Easy - EllysJuice (×)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11843&rd=15090

・アップルジュースとオレンジジュースが1ガロンずつある。
・プレイヤーは順番に交互のジュースを半分ずつ飲んでいく。
・ここで、プレイヤーの集合が与えられる。ただし、実際に飲んだ順番はわかっていない。
・このとき、存在しうる一番ジュースを飲んだプレイヤーを求める。
・ただし、一番ジュースを飲んだ量が同じであるプレイヤーが複数存在した場合は
 勝者は存在しない。

解き方


・プレイヤー数は8なので、全探索ができそう。
・ただし、実装が若干大変。
・そこで問題文から、複数名前が存在するプレイヤー、もしくはプレイヤーの数が1人のとき
 そのプレイヤーが勝者になることがわかる。
・これがわかれば、実装するだけ。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class EllysJuice {

public: vector<string> getWinners(vector<string> players) {
int n=players.size();
int maxn=0;
map<string,int> m;

FORE(i,0,n){
m[players[i]]++;
maxn=max(maxn,m[players[i]]);
}

vector<string> ans;
if(maxn>=2){
for(map<string,int>:: iterator it=m.begin();it!=m.end();it++){
if(it->second>=2)ans.push_back(it->first);
}
}
else if(n==1){
ans.push_back(players[0]);
}
sort(all(ans));

return ans;
}

};
このエントリーをはてなブックマークに追加