Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2206-88af7544
この記事にトラックバックする(FC2ブログユーザー)

SRM529 DIV1 EASY/DIV2 MEDIUM - KingSort (この記事を編集する[管理者用])

Source

TopCoder SRM529 DIV1 EASY (250pt)
TopCoder SRM529 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

N人 (50以下) の王様の名前が与えられる.
王様の名前は,
 アルファベット大文字1文字+アルファベット小文字で何文字か+半角スペース1文字+50未満のローマ数字
というフォーマットになっている.
半角スペースより前のアルファベットの早い順,アルファベット部分が同じなら,ローマ数字の小さい順にソートする問題.

解法

やるだけ.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

int romanNumberToInt(const char c[],int len){
  int i,n=0;
  rep(i,len){
    if(i<len-1 && c[i]=='C' && c[i+1]=='M'){n+=900; i++; continue;}
    if(i<len-1 && c[i]=='C' && c[i+1]=='D'){n+=400; i++; continue;}
    if(i<len-1 && c[i]=='X' && c[i+1]=='C'){n+=90; i++; continue;}
    if(i<len-1 && c[i]=='X' && c[i+1]=='L'){n+=40; i++; continue;}
    if(i<len-1 && c[i]=='I' && c[i+1]=='X'){n+=9; i++; continue;}
    if(i<len-1 && c[i]=='I' && c[i+1]=='V'){n+=4; i++; continue;}
    if(c[i]=='M') n+=1000;
    else if(c[i]=='D') n+=500;
    else if(c[i]=='C') n+=100;
    else if(c[i]=='L') n+=50;
    else if(c[i]=='X') n+=10;
    else if(c[i]=='V') n+=5;
    else if(c[i]=='I') n++;
  }
  return n;
}

class KingSort {
public:
vector <string> getSortedList(vector <string> kings) {
  int i,j,k;
  vector <string> res;
  vector< vector<string> > st;

  rep(i,kings.size()){
    string name, num;
    int n;
    char buf1[100], buf2[100];
    vector<string> add;

    sscanf(kings[i].c_str(),"%s%s",buf1,buf2);
    name = buf1;
    num = buf2;

    n = romanNumberToInt(num.c_str(), num.size());
    sprintf(buf1,"%04d",n);
    num = buf1;

    add.push_back(name);
    add.push_back(num);
    add.push_back(kings[i]);
    st.push_back(add);
  }

  sort(st.begin(), st.end());
  rep(i,st.size()) res.push_back(st[i][2]);

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2206-88af7544
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。