SRM 265 DIV1 Easy - ScheduleStrength (復習○)

February 08, 2014

問題

複数のチームがあり対戦を行う。
総当たり戦ではなく、対戦しないチーム同士もある。

ここで、各チームの強さを求めたい。

あるチームの強さは、対戦した他のチーム全てに対し、
「他のチームの勝ち数／他のチームの勝ち数＋他のチームの負け数」
が少ないほど強いチームにある。

ただし、他のチームの勝ち数からは自チームの負け数、他のチームの負け数からは自チームの勝ち数を引いてカウントしなければならない。

このとき、各チームを強さの順にソートして返す。強さが同じ時はチーム名の昇順に並べる。

解き方

シミュレーション問題なので、いかにシンプルにコーディングするか。

いきなり計算してもよいのですが、各チームの勝ち負け数をカウントしてから
強さを計算することでシンプルに実装できます。

コード

#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 ScheduleStrength {

public: vector<string> calculate(vector<string> teams, vector<string> results) {
int n=teams.size();
int win[n],lose[n];

memset(win,0,sizeof(win));
memset(lose,0,sizeof(lose));

FORE(i,0,n){
FORE(j,0,n){
if(results[i][j]=='W')win[i]++;
if(results[i][j]=='L')lose[i]++;
}
}

vector<pair<pair<double,string>,int> > p;
FORE(i,0,n)p.push_back(make_pair(make_pair(1.0,teams[i]),0));

FORE(i,0,n){
double c1=0.0,c2=0.0;
FORE(j,0,n)if(results[i][j]!='-'){
c1+=win[j];
c2+=lose[j];
}
c1-=lose[i],c2-=win[i];
if(c1+c2!=0.0)p[i].first.first-=c1/(c1+c2);
}
sort(all(p));

vector<string> ans;
FORE(i,0,n)ans.push_back(p[i].first.second);

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 ScheduleStrength {

public: vector<string> calculate(vector<string> teams, vector<string> results) {
int n=teams.size();
int win[n],lose[n];
memset(win,0,sizeof(win));
memset(lose,0,sizeof(lose));

FORE(i,0,n){
FORE(j,0,n){
if(results[i][j]=='W')win[i]++;
if(results[i][j]=='L')lose[i]++;
}
}

double score[n];
FORE(i,0,n){
int w=-lose[i],l=-win[i];
FORE(j,0,n)if(results[i][j]!='-')w+=win[j],l+=lose[j];
score[i]=(double)w/(w+l);
}

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

return teams;
}

};

実装