SRM 171 DIV1 Easy - CrossCountry (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=1950&rd=4660
・チーム数と、ゴールしたメンバーのチーム名が到着順に与えられる。
・チームのスコアは最初にゴールした５人の到着順の和になる。
ゴールした人数が５人未満のチームはカウント対象にならない。
・スコアの小さい順にチームを並べる。
スコアが同じとき、６人目のゴール者がいる場合はその到着が早い方が先になる。
６人目のゴール者がいない場合は６人目のゴール者がいる方が先になる。
それでも同一の場合は、チーム名の昇順になる。
このとき、チーム名を順番に並べた文字列を返す。
解き方
ソートの方法が複雑なので、独自にソート順を定義する。
こちらを参考にさせていただきました。
http://d.hatena.ne.jp/minus9d/20130501/1367415668
コード
class CrossCountry {
public:
struct team{
int score;
int sixth;
char name;
bool operator<(const team & a)const{
if(score!=a.score)return score<a.score;
if(sixth!=a.sixth)return sixth<a.sixth;
return name<a.name;
}
};
string scoreMeet(int numTeams, string finishOrder) {
vector<team> teams;
string ans="";
FORE(i,0,numTeams){
team t;
t.score=0;
t.sixth=10000;
t.name='A'+i;
int num=0;
FORE(j,0,finishOrder.size()){
if(('A'+i)==finishOrder[j]){
if(num<5)t.score+=j;
else if(num==5)t.sixth=j;
num++;
}
}
if(num>=5)teams.push_back(t);
}
sort(all(teams));
FORE(i,0,teams.size())ans+=teams[i].name;
return ans;
}
};
public:
struct team{
int score;
int sixth;
char name;
bool operator<(const team & a)const{
if(score!=a.score)return score<a.score;
if(sixth!=a.sixth)return sixth<a.sixth;
return name<a.name;
}
};
string scoreMeet(int numTeams, string finishOrder) {
vector<team> teams;
string ans="";
FORE(i,0,numTeams){
team t;
t.score=0;
t.sixth=10000;
t.name='A'+i;
int num=0;
FORE(j,0,finishOrder.size()){
if(('A'+i)==finishOrder[j]){
if(num<5)t.score+=j;
else if(num==5)t.sixth=j;
num++;
}
}
if(num>=5)teams.push_back(t);
}
sort(all(teams));
FORE(i,0,teams.size())ans+=teams[i].name;
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 CrossCountry {
public:
string scoreMeet(int numTeams, string finishOrder) {
int n=finishOrder.size();
string name[numTeams];
int score[numTeams],num[numTeams],fast[numTeams];
memset(score,0,sizeof(score));
memset(num,0,sizeof(num));
FORE(i,0,numTeams)fast[i]=1e+9;
FORE(i,0,numTeams)name[i]=('A'+i);
FORE(i,0,n){
num[finishOrder[i]-'A']++;
if(num[finishOrder[i]-'A']<=5)score[finishOrder[i]-'A']+=i+1;
if(num[finishOrder[i]-'A']==6)fast[finishOrder[i]-'A']=i+1;
}
FORE(i,0,numTeams)if(num[i]<=4)score[i]=1e+9;
FORE(i,0,numTeams)for(int j=numTeams-1;j>=i+1;j--){
if(score[j]<score[j-1]||(score[j]==score[j-1]&&fast[j]<fast[j-1])||(score[j]==score[j-1]&&fast[j]==fast[j-1]&&name[j]<name[j-1])){
swap(name[j-1],name[j]);
swap(score[j-1],score[j]);
swap(num[j-1],num[j]);
swap(fast[j-1],fast[j]);
}
}
string ret="";
FORE(i,0,numTeams)if(score[i]!=1e+9)ret+=name[i];
return ret;
}
};
#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 CrossCountry {
public:
string scoreMeet(int numTeams, string finishOrder) {
int n=finishOrder.size();
string name[numTeams];
int score[numTeams],num[numTeams],fast[numTeams];
memset(score,0,sizeof(score));
memset(num,0,sizeof(num));
FORE(i,0,numTeams)fast[i]=1e+9;
FORE(i,0,numTeams)name[i]=('A'+i);
FORE(i,0,n){
num[finishOrder[i]-'A']++;
if(num[finishOrder[i]-'A']<=5)score[finishOrder[i]-'A']+=i+1;
if(num[finishOrder[i]-'A']==6)fast[finishOrder[i]-'A']=i+1;
}
FORE(i,0,numTeams)if(num[i]<=4)score[i]=1e+9;
FORE(i,0,numTeams)for(int j=numTeams-1;j>=i+1;j--){
if(score[j]<score[j-1]||(score[j]==score[j-1]&&fast[j]<fast[j-1])||(score[j]==score[j-1]&&fast[j]==fast[j-1]&&name[j]<name[j-1])){
swap(name[j-1],name[j]);
swap(score[j-1],score[j]);
swap(num[j-1],num[j]);
swap(fast[j-1],fast[j]);
}
}
string ret="";
FORE(i,0,numTeams)if(score[i]!=1e+9)ret+=name[i];
return ret;
}
};
