SRM529 Div1 Easy - KingSort

問題

王様の名前がn個与えられ、i番目の名前はs[i]である
これを昇順にソートせよ
ただし王様の名前は「(名前) (番号)」という構成になっていて、番号はアルファベット順ではなく数字順に並べる必要がある
(例えば "Louis IX" と "Louis VIII" では文字列自体は前者の方が小さいけど今回は後者の方が小さいことになる)

1 <= n <= 50
1 <= |s[i]| <= 20
1 <= (王様の番号) <= 50

解法

王様の名前を{名前(string), 番号(int)}というペアに変換し、それで昇順ソートしてからまた文字列に戻す
番号をstringからintに変換するのは全部試してみるような実装をするとちょっと楽(↓のコードのnumメソッド)

class KingSort {
public:
	string d[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
	string dd[6] = {"", "X", "XX", "XXX", "XL", "L"};

	int num(string &s) {
		rep(i,10) rep(j,6) {
			string t = dd[j] + d[i];
			if (s==t) return j*10 + i;
		}
		return -1;
	}

	vector<string> getSortedList(vector<string> s) {
		vector<pair<string,int> > t;
		each(i,s) {
			string x;
			rep(j,i.size()) {
				if (i[j]==' ') {
					string y = i.substr(j+1);
					t.push_back({x, num(y)});
				} else x.push_back(i[j]);
			}
		}
		sort(all(t));
		vector<string> res;
		each(i,t) res.push_back(i.first + " " + dd[i.second/10] + d[i.second%10]);
		return res;
	}
};