Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-04-25

久しぶりに過去問練習。Algorithm Tutorialsを見ながら過去問を解くの巻。

SRM236 Div1 Easy: BusinessTasks

| 05:28 | SRM236 Div1 Easy: BusinessTasks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM236 Div1 Easy: BusinessTasks - naoya_t@topcoder SRM236 Div1 Easy: BusinessTasks - naoya_t@topcoder のブックマークコメント

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

Straight-forward problems that don't require any special technique の例として挙げられている問題。

  • vectorのn番目の要素を消して詰めるにはどうしたらいいか、というSTL操作的な問題でつまづくなどするが
  • 216.06点ということは11'38'' …これは遅い
#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 BusinessTasks {
 public:
  string getTask(vector<string> list, int n) {
    n--;
    int N=sz(list),l=N,cur=0;
    rep(i,N-1){
      cur=(cur+n)%l;
      list.erase(list.begin()+cur);
      l--;
    }
    return list[0];
  }
};

もうちょっとまとめて

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

class BusinessTasks {
 public:
  string getTask(vector<string> list, int n) {
    n--;
    for(int N=sz(list),cur=0;N>1;N--){
      cur=(cur+n)%N;
      list.erase(list.begin()+cur);
    }
    return list[0];
  }
};
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090425