naoya_t@topcoder

SRM236 Div1 Easy: BusinessTasks

過去問, 練習, Tutorials | 05:28 |

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];
  }
};