問題
http://community.topcoder.com/stat?c=problem_statement&pm=8607&rd=11127
解き方
問題分の通り実装し、収束するまで繰り返せば良い。
コード
class InstantRunoffVoting {
public: int winner(vector<string> voters) {
int n=voters.size(),m=voters[0].size();
int used[10],v[10];
memset(used,0,sizeof(used));
while(1){
memset(v,0,sizeof(v));
int finish=1;
FORE(i,0,m)if(used[i]==0)finish=0;
if(finish)break;
FORE(i,0,n){
int idx=0;
while(used[voters[i][idx]-'0']==1)idx++;
v[voters[i][idx]-'0']++;
}
FORE(i,0,m)if(v[i]>n*0.5)return i;
int mx=100;
FORE(i,0,m)if(used[i]==0)mx=min(mx,v[i]);
FORE(i,0,m)if(v[i]==mx)used[i]=1;
}
return -1;
}
};
public: int winner(vector<string> voters) {
int n=voters.size(),m=voters[0].size();
int used[10],v[10];
memset(used,0,sizeof(used));
while(1){
memset(v,0,sizeof(v));
int finish=1;
FORE(i,0,m)if(used[i]==0)finish=0;
if(finish)break;
FORE(i,0,n){
int idx=0;
while(used[voters[i][idx]-'0']==1)idx++;
v[voters[i][idx]-'0']++;
}
FORE(i,0,m)if(v[i]>n*0.5)return i;
int mx=100;
FORE(i,0,m)if(used[i]==0)mx=min(mx,v[i]);
FORE(i,0,m)if(v[i]==mx)used[i]=1;
}
return -1;
}
};