SRM 529 Div2 Medium KingSort

問題

与えられた文字列リストをソートせよ.各文字列は名前+スペース+ローマ数字となっているので同じ名前の場合,数字が小さいものから並べよ.

解答

ローマ数字を解釈する処理が面倒なだけでそれさえ出来れば,後はナイーブにソートしてやるだけ.

class KingSort
{
public:
  vector <string> getSortedList(vector <string> kings)
    {
      vector<int> nums;
      vector<string> names;
      int n = kings.size();
      int i, j;
      for(i = 0; i < n; i++){
        int rnum = 0;
        j = kings[i].find(' ')+1;
        names.push_back(kings[i].substr(0, j));
        if (kings[i].substr(j, 3) == "XXX"){ rnum += 30; j+=3;}
        else if (kings[i].substr(j, 2) == "XX") {rnum += 20; j += 2;}
        else if (kings[i].substr(j, 2) == "XL") {rnum += 40; j += 2;}
        else if (kings[i][j] == 'X') {rnum += 10; j++;}
        else if (kings[i][j] == 'L') {rnum += 50; j++;}
        // if (kings[i][j] == 'X') rnum += 10;

        if (kings[i].substr(j, 4) == "VIII") rnum += 8;
        else if (kings[i].substr(j, 3) == "III") rnum += 3;
        else if (kings[i].substr(j, 3) == "VII") rnum += 7;
        else if (kings[i].substr(j, 2) == "VI") rnum += 6;
        else if (kings[i].substr(j, 2) == "IV") rnum += 4;
        else if (kings[i].substr(j, 2) == "IX") rnum += 9;
        else if (kings[i].substr(j, 2) == "II") rnum += 2;
        else if (kings[i][j] == 'I') rnum += 1;
        else if (kings[i][j] == 'V') rnum += 5;
        nums.push_back(rnum);
      }
      vector<string> ret;
      vector<int> idx;
      for(i = 0; i < n; i++) idx.push_back(i);
      for(i = 0; i < n; i++){
        for(j = i+1; j < n; j++){
          if (names[idx[i]] > names[idx[j]] || (names[idx[i]] == names[idx[j]] && nums[idx[i]] > nums[idx[j]])){
            int tmp = idx[i];
            idx[i] = idx[j];
            idx[j] = tmp;
          }
        }
        ret.push_back(kings[idx[i]]);
      }
      return ret;
    }
};