topcoder

naoya_t@topcoder

2009-04-26

SRM209 Div1 Easy (300pt): MedalTable

過去問, 練習, Tutorials | 00:46 |

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

過去問, 練習, Tutorials | 00:13 |

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

自家製 split(), map_atoi() を使用
最初、答えの第２要素を各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;
  }
};

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090426