SRM620 Div2Easy CandidatesSelectionEasy

概要
メイドを雇いたいと考えている。vector score があるとき、scroe[i][j] は、技術 j に対して候補者 i の能力の評価を示す。評価は'A'評価を最も良いとして、最も悪い'Z'評価まである。
雇いたいメイドは技術 x が良い評価であればよい。このとき雇いたいメイドをランキング付けよ。技術 x が同じ評価の場合、候補者番号を昇順で見て優先的にランキング付けをするものとする。

解法
一番簡単と思えるのが、全候補者のうち、score[i][x] だけ見て、その評価と番号のpairをvectorにつっこんでソートする。嫌がらせかどうかメソッド名が sort() とかいう名前をしているので、std::sort() というように名前空間を指定してやると良い。
また、安定ソートであるマージソート( stable_sort() )を用いても良いと思う。

反省
問題文読解に手こずったのでコードも下手な書き方をしている。候補者番号で見て昇順とすぐに分からず迷走した。

良いコード

// container utility
#define ALL(x) (x).begin(), (x).end()
#define MP make_pair
#define PB push_back
typedef vector<int> VI;
class CandidatesSelectionEasy {
public:
  vector <int> sort(vector <string> score, int x) {
    vector<pair<char, int> > vec;
    for(int i=0; i<score.size(); i++) {
      vec.PB(MP(score[i][x], i));
    }
    std::sort(ALL(vec));
    VI ret;
    for(int i=0; i<score.size(); i++) {
      ret.PB(vec[i].second);
    }
    return ret;
  }
};

本番中のコード

// rep
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class CandidatesSelectionEasy {
public:
  vector <int> sort(vector <string> score, int x) {
    int N = score.size(), M = score[0].size();
    vector<int> ret;
    
    set<int> used;
    while(1) {
      int idx;
      int mn = 100;
      bool update = false;
      for(int i=0; i<N; i++) {
        if((int)score[i][x] < mn && !used.count(i) ) {
          update = true;
          mn = score[i][x];
          idx = i;
        }
      }
      if(!update) break;
      ret.push_back(idx);
      used.insert(idx);
    }
    
    return ret;
  }
};