SRM 207 DIV1 Easy - RegularSeason (復習○)

January 25, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=2866&rd=5853

・複数のチームが総当たりで対戦する。
・各チームは与えられた対戦数をホーム・アウェーで対戦する。
・対戦する際の勝率が与えられる。
・勝つ試合数は勝率＊対戦数の和を最後に四捨五入(round up)したものになる。
・最後に勝った試合数の降順、同じ場合は四捨五入前の勝った試合数の降順、それも同じ場合はチーム名の昇順で”チーム名　勝った試合数”のフォーマットで返す。

解き方

勝率の求め方が少しわかりにくくて苦労しました。
最後のソートは構造体のソートを書きましたが、
四捨五入前の数字があれば勝った試合数の降順は使わなくてもよいことに気づけばもっと単純にかけました。

計算ごとに１００で割るのではなく、最後に１００で割るのが丸め誤差を防ぐポイント。

コード

class RegularSeason {

public:

struct team{
double points;
int score;
string name;

bool operator<(const team & v)const{
if(score!=v.score)return score>v.score;
if(points!=v.points)return points>v.points;
return name<v.name;
}
};

vector<string> finalStandings(vector<string> teams, int rounds) {
int n=teams.size();
vector<team> t(n);
vector<string> ans(n,"");

FORE(i,0,n){
stringstream out(teams[i]);
out>>t[i].name;
FORE(j,0,n){
double num;
out>>num;
if(i==j)continue;
else{
t[i].points+=num*rounds;
t[j].points+=(100-num)*rounds;
}
}
}

FORE(i,0,n){
t[i].points/=100.0;
t[i].score=t[i].points+0.5;
}
sort(all(t));

FORE(i,0,n){
char ch[100];
sprintf(ch,"%s %d",t[i].name.c_str(),t[i].score);
ans[i]=ch;
}

return ans;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class RegularSeason {

public:

vector<string> finalStandings(vector<string> teams, int rounds) {
int n=teams.size();
string name[n];
double score[n];
FORE(i,0,n)score[i]=0;

FORE(i,0,n){
stringstream out(teams[i]);
out>>name[i];
FORE(j,0,n){
int p;
out>>p;
if(i==j)continue;
score[i]+=(double)p*rounds;
score[j]+=(double)(100-p)*rounds;
}
}

FORE(i,0,n)for(int j=n-1;j>=i+1;j--){
if(score[j-1]<score[j]||(score[j-1]==score[j]&&name[j-1]>name[j])){
swap(score[j-1],score[j]);
swap(name[j-1],name[j]);
}
}

vector<string> ans;
FORE(i,0,n){
char ch[100];
sprintf(ch,"%s %d",name[i].c_str(),(int)(score[i]/100+0.5));
ans.push_back(ch);
}

return ans;
}

};

実装