SRM 529 DIV1 Easy - KingSort (復習×○)

September 29, 2013

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11740&rd=14722

王様の名前が与えられ、順番に並べる。
名前はアルファベットの連続とＩ，ＩIの数字で与えられ、アルファベットの昇順、同じ場合はＩ，ＩIの小さい順になる。
名前が与えられた時、ソート後の順列を返す。

解き方

シミュレーション問題。
数字側の規則が多いので、ここをいかに簡略化できるか。

今回のコツは以下の３つ。
①判定が多い場合は配列にパターンを格納し判定。
②与えられた文字列を分解して判別するのではなく、全てのパターンを作りマッチするものを返す。
③ソートの要素が２つあるときは、pairを２回入れ子にし最初のpairを判定の順番に格納する。

計算量はＯ（70*50*50*2=3.5*10^5）。

コード

class KingSort {

public:

int calc(string s){
string c1[]={"","I","II","III","IV","V","VI","VII","VIII","IX"};
string c10[]={"","X","XX","XXX","XL","L"};
int num=0;

FORE(i,0,10)FORE(j,0,6){
if(i==0&&j==0)continue;
if(c10[j]+c1[i]==s){
num=j*10+i;
break;
}
}

return num;
}

vector<string> getSortedList(vector<string> kings) {
int n=kings.size();
vector<pair<pair<string,int>,string> > vx(n);
vector<string > ans(n);

FORE(i,0,kings.size()){
string tmp1,tmp2;
stringstream out(kings[i]);
out>>tmp1;
out>>tmp2;
vx[i].first.first=tmp1;
vx[i].first.second=calc(tmp2);
vx[i].second=kings[i];
}
sort(vx.begin(),vx.end());

FORE(i,0,n)ans[i]=vx[i].second;

return ans;
}

};

実装