Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-20

SRM381 div2 (過去問)

01:17

Easy - TheBestName

stringの集合をある方法でソートする問題.

struct を作り, 要件を満たすように operator< をオーバーロードし, ソートしました. ただ回答のメソッド名が"sort"だったため, std::sort と名前が衝突していて, ネームスペースを指定してあげないと std の方の sort() が呼べません. このことに気付かず20分くらいはまってしまいました. topcoder では時間節約のために using namespace std しているので発見に時間がかかってしまいました. これにはかなりがっくりきました.

typedef struct node {
  int weight;
  string name;
};

bool operator< (const node &a, const node &b) {
  if (a.weight == b.weight)
    return a.name < b.name;
  else
    return a.weight > b.weight;
}

class TheBestName {
public:
  vector <string> sort(vector <string> names) {
    vector <string> ret;
    vector <node> nodes;
    int number_of_john = 0;

    for (unsigned int i=0; i<names.size(); i++) {
      if (names[i] == "JOHN") {
        number_of_john++;
        continue;
      }
      node a;
      a.weight = 0;
      a.name = names[i];
      for (unsigned int j=0; j<names[i].size(); j++)
        a.weight += names[i][j] - 'A' + 1;
      nodes.push_back(a);
    }

    std::sort(nodes.begin(), nodes.end());

    for (int i=0; i<number_of_john; i++)
      ret.push_back("JOHN");

    for (unsigned int i=0; i<nodes.size(); i++)
      ret.push_back(nodes[i].name);

    return ret;
  }
};