TopCoder SRM 393 Div1 Easy InstantRunoffVoting

問題

n人の人が、m人の候補に対して投票して、一人の代表を決定する。
投票は次のルールで行われる。

最初、n人はそれぞれm人に対して順位をつける。
残っている人が二人以上の間、

• n人は残っている人の中でつけた順位が最も高い人に投票する。
• 過半数の票を獲得した人がいたらその人が代表になる。
• そうでないとき、票数が最も少なかった人（複数いた場合全員）を候補から消す。
• 全員がタイだった場合、代表者はなし。

各人がつけた順位があたえられるとき、代表として選ばれる人をもとめよ。
代表者がいなかった場合は-1を返せ。

制約条件

n≦50
m≦10

方針

定義にしたがって実装する。

ソースコード

class InstantRunoffVoting {
  public:
  int winner(vector <string> voters) {
    vi cand;
    int n=voters.size(), m=voters[0].size();
    rep(i,m)cand.pb(i);
    while(cand.size()>1){
      m=cand.size();
      vector<pi> vote(m);
      rep(i,m)vote[i]=mp(0,cand[i]);
      rep(i,n){
        rep(j,voters[0].size())rep(k,m)if(vote[k].second==voters[i][j]-'0'){
          vote[k].first++; goto NEXT;
        }
        NEXT:;
      }
      sort(all(vote));
      if(vote[m-1].first*2>n)cand=vi(1,vote[m-1].second);
      else{
        int p=0;
        for(;p<m&&vote[0].first==vote[p].first;p++){
          rep(i,cand.size())if(cand[i]==vote[p].second)cand.erase(cand.begin()+i);
        }
      }
    }
    return cand.empty()?-1:cand[0];
  }
};