Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-04-26

SRM209 Div1 Easy (300pt): MedalTable

| 00:46 | SRM209 Div1 Easy (300pt): MedalTable - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM209 Div1 Easy (300pt): MedalTable - naoya_t@topcoder SRM209 Div1 Easy (300pt): MedalTable - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

  • 自家製 split() を使用
  • mapでエラーが出るので使い方忘れた?と思ったらmという変数をintでも使ってたorz
  • 240.55 points(14'54''), Passed system test.
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

class MedalTable {
 public:
  vector<string> generate(vector<string> results) {
    int rn=sz(results);
    map<string,int> m;
    rep(i,rn){
      vector<string> cs=split(results[i]);
      for(int j=0,mk=4096;j<3;j++,mk>>=6){
        string cnt=cs[j];
        if(found(m,cnt)){
          m[cnt]+=mk;
        }else{
          m[cnt]=mk;
        }
      }
    }
    vector<pair<int,string> > sc;
    tr(m,it){
      sc.pb(make_pair(-it->second,it->first));
    }
    sort(all(sc));
    vector<string> ret;
    tr(sc,it){
      stringstream ss;
      ss << it->second << " ";
      int score=-it->first;
      ss << (score >> 12) << " " << ((score >> 6) & 63) << " " << (score & 63);
      ret.pb(ss.str());
    }
    return ret;
  }
};

SRM208 Div1 Easy: TallPeople

| 00:13 | SRM208 Div1 Easy: TallPeople - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM208 Div1 Easy: TallPeople - naoya_t@topcoder SRM208 Div1 Easy: TallPeople - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

  • 自家製 split(), map_atoi() を使用
  • 最初、答えの第2要素を各rowの最大の最小で見ていて数が合わなかったのは秘密
  • 224.02points (=9'54''), passed system test
  • 自家製ライブラリとか、ポイントと所要時間の相互変換スクリプトとか GitHubに置いてるので良かったら見てね
#define sz(a)  int((a).size())
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

class TallPeople {
 public:
  vector<int> getPeople(vector<string> people) {
    int rows=sz(people),cols=0;
    vector<vector<int> > nums(rows);
    rep(row,rows){
      nums[row] = map_atoi(split(people[row]));
      cols=sz(nums[row]);
    }
    int ts=0;
    rep(r,rows){
      vector<int> row(all(nums[r]));
      sort(all(row));
      int s=row[0]; if(s>ts) ts=s;
    }
    int st=INT_MAX;
    rep(c,cols){
      vector<int> col(rows);
      rep(r,rows) col[r]=nums[r][c];
      sort(all(col));
      int t=col[rows-1]; if(t<st) st=t;
    }
    vector<int> ret(2);
    ret[0]=ts, ret[1]=st;
    return ret;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090426