Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-26

SRM393 Div1 Easy: InstantRunoffVoting

| 06:39 | SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder SRM393 Div1 Easy: InstantRunoffVoting - naoya_t@topcoder のブックマークコメント

問題文のルールを素直にコーディングしたら解ける問題。のはずがちょっと手間取り。

vector<int> voからvo[0]の値と同じ値の要素をすべて捨てるための自作マクロremove_()を使っているが、remove_(vo,vo[0])は予期しない結果を生む。これでハマった。

あと、得票ゼロの候補者を捨て忘れていてシステムテストに引っかかるなど。

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class InstantRunoffVoting {
public:
  int winner(vector<string> voters) {
    int population=sz(voters), // 1-50
      N=voters[0].length(); //1-10
    set<int> s; rep(i,N) s.insert(i);
    while(sz(s)>0){
      vector<int> votes(N,0);
      rep(p,population){
        rep(i,N) {
          int c=voters[p][i]-'0';
          if(found(s,c)) { votes[c]++; break; }
        }
      }
      vector<int> vo(all(votes));
      rep(i,N) if(votes[i]==0) s.erase(i); //これが抜けてた
      remove_(vo,0);
      sort(all(vo));
      if(sz(vo)==0) return -1;
      if(sz(vo)==1) rep(i,N) if(votes[i]==vo[0]) return i;
      int minvote=vo[0];
      rep(i,N) if(votes[i]==minvote) s.erase(i);
      remove_(vo,minvote); // ※
      if(sz(vo)==0) return -1;
      if(sz(vo)==1) rep(i,N) if(votes[i]==vo[0]) return i;
    }
  }
};