naoya_t@topcoder

過去問マラソン(#14):SRM154(続き)

過去問マラソン | 13:32 |

• １ヶ月ぶり

Medium(500): ContestScore

• 一見難しくなさそうなんだけど
• まんまと罠にひっかかりました

初回投稿：

• 290.96 (28'52'')

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class ContestScore {

 public:
  vector <string> sortResults(vector <string> data) {
	int n=sz(data);//0-50
    vector<vector<double> > scores(n,vector<double>());
    vector<string> groupnames(n);
    int judges = 0;
    rep(i,n){
      istringstream ss(data[i]);
      ss >> groupnames[i];
      if (judges) {
        rep(j,judges) { double tmp; ss >> tmp; scores[i].pb(tmp); }
      } else {
        while (!ss.eof()) { double tmp; ss >> tmp; scores[i].pb(tmp); judges++; }
      }
    }

    vector<vector<int> > ranks(n,vector<int>(judges) );
    rep(j,judges){
      vector<pair<double,int> > jscores(n);
      rep(i,n) jscores[i] = make_pair(-scores[i][j], i);
      sort(all(jscores));

      int lastrank = 1, rankcnt = 1; double lastscore = jscores[0].first;
      vector<int> jranks(n);
      rep(i,n) {
        if (jscores[i].first == lastscore) {
          jranks[ jscores[i].second ] = lastrank;
        } else {
          jranks[ jscores[i].second ] = rankcnt; lastrank = rankcnt;
        }
        rankcnt++; lastscore = jscores[i].first;
      }
      rep(i,n) ranks[i][j] = jranks[i];
    }

    vector<int> ranksum(n,0); vector<double> scoresum(n,0);
    vector<pair<int,pair<double,string> > > thescore(n);
    
    rep(i,n) {
      rep(j,judges) {
        ranksum[i] += ranks[i][j];
        scoresum[i] += scores[i][j];
      }
      thescore[i] = make_pair(ranksum[i],make_pair(-scoresum[i],groupnames[i]));
    }
    sort(all(thescore));

    vector<string> ans;
    rep(i,n) {
      stringstream ss;
      ss << thescore[i].second.second << " " << thescore[i].first << " " << -thescore[i].second.first;
      bool point=false;
      tr(ss.str(),it){
        if (*it == '.') {point=true;break;}
      }
      if (!point) ss << ".0";
      ans.pb(ss.str());
    }
    return ans;
  }
};

• failed system test
• 小数点以下第一位が0のときに「.0」を表示するようにしたつもりだったけど、サーバでは効いてなかった。（なぜだろう）
• その箇所を

      char buf[256];
      sprintf(buf, "%s %d %3.1f",
              thescore[i].second.second.c_str(),
              thescore[i].first,
              -thescore[i].second.first);
      ans.pb(buf);

• 別の問題が発生

FAILED (0.446 msec)
	Expected: { "A 22 594.8","AA 34 483.7","AAA 34 466.2","AAAA 46 395.1","AAAAA 46 395.1","AAAAAA 48 387.6","AAAAAAA 48 387.6","AAAAAAAA 49 371.5","AAAAAAAAA 52 304.3","AAAAAAAAAA 54 348.6", }
	Received: { "A 22 594.8","AA 34 483.7","AAA 34 466.2","AAAA 46 395.1","AAAAA 46 395.1","AAAAAAA 48 387.6","AAAAAA 48 387.6","AAAAAAAA 49 371.5","AAAAAAAAA 52 304.3","AAAAAAAAAA 54 348.6", }

• なにこれ
• rank合計もscore合計も同じ、で文字列比較でAAAAAA<AAAAAAAになるのが期待されるところ</li>
• sortを比較関数渡し型にしてみた
• score合計のところで異常。
  • 同じ数字に見えて 1.13687e-13 の差がある
  • なるほどそういうことか
  • スコアを全部10倍にして整数で保存するぞ！結果出力時に0.1掛けすればよいさ

最終投稿

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

typedef pair<int,pair<int,string> > score_t;
#define make_score(R,S,N) make_pair(R,make_pair(S,N))
#define car first
#define cdr second
#define caar first.first
#define cdar first.second
#define cadr second.first
#define cddr second.second

bool cmp(score_t s1, score_t s2) {
  if (s1.car < s2.car) return true;
  if (s1.car > s2.car) return false;
  
  if (s1.cadr > s2.cadr) return true;
  if (s1.cadr < s2.cadr) return false;

  return s1.cddr < s2.cddr;
}

class ContestScore {

 public:
  vector <string> sortResults(vector <string> data) {
    int n=sz(data);//0-50
    if (n==0) return vector<string>();
    
    vector<vector<int> > scores(n,vector<int>());
    vector<string> groupnames(n);

    rep(i,n){
      istringstream ss(data[i]);
      ss >> groupnames[i];
      while (!ss.eof()) {
        double tmp; ss >> tmp;
        scores[i].pb((int)(tmp*10 + 0.5));
      }
    }
    int judges = sz(scores[0]);

    vector<vector<int> > ranks(n,vector<int>(judges) );
    rep(j,judges){
      vector<pair<int,int> > jscores(n);
      rep(i,n) jscores[i] = make_pair(-scores[i][j], i);
      sort(all(jscores));

      int lastrank = 1, rankcnt = 1; int lastscore = jscores[0].first;
      vector<int> jranks(n);
      rep(i,n) {
        if (jscores[i].first == lastscore) {
          jranks[ jscores[i].second ] = lastrank;
        } else {
          jranks[ jscores[i].second ] = rankcnt; lastrank = rankcnt;
        }
        rankcnt++; lastscore = jscores[i].first;
      }
      rep(i,n) ranks[i][j] = jranks[i];
    }

    vector<int> ranksum(n,0); vector<int> scoresum(n,0);
    vector<score_t> thescore(n);
    
    rep(i,n) {
      rep(j,judges) {
        ranksum[i] += ranks[i][j];
        scoresum[i] += scores[i][j];
      }
      thescore[i] = make_pair(ranksum[i],make_pair(scoresum[i],groupnames[i]));
    }
    sort(all(thescore),cmp);

    vector<string> ans;
    rep(i,n) {
      char buf[256];
      sprintf(buf, "%s %d %3.1f",
              thescore[i].cddr.c_str(),
              thescore[i].car,
              0.1 * thescore[i].cadr);
      ans.pb(buf);
    }
    return ans;
  }
};

• passed system test
• ふぅ