Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-17

SRM219 Div1 Medium: TurntableService

| 23:03 | SRM219 Div1 Medium: TurntableService - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM219 Div1 Medium: TurntableService - naoya_t@topcoder SRM219 Div1 Medium: TurntableService - naoya_t@topcoder のブックマークコメント

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

  • split(), map_atoi() は拙作ライブラリ
  • 1つ以上左(ないし右)に回した各状態、回さずに目の前の料理を取った状態をpriority_queueに追加。
  • 前回が回転なら料理をとる。前回料理を取ったなら回転。(というフラグを渡す)
  • あとはTLEとの戦い
  • priority_queue, map, set などに入れる情報は可能なら単一のintとかに詰めたほうがよい
    • ssssssssssssoooofeeeeeeeeeeeeeee
      • s:そこまでにかかった秒数(<=12bit)
      • o:回転オフセット([0..N-1]<=4bit)
      • f:前回料理を取った(ので回転したい)かどうか(1bit)
      • e:各人が好物を既に1つ以上食べているか(N<=15bit)
class TurntableService {
 public:
  int calculateTime(vector <string> favorites) {
    int n=sz(favorites); // 1-15
    int ful = (1<<n)-1;
    vector<vector<bool> > fav(n);
    rep(i,n){
      vi f = map_atoi(split(favorites[i]));
      fav[i].resize(n); rep(j,n) fav[i][j]=false;
      tr(f,it) fav[i][*it]=true;
    }
    set<int> s;
    priority_queue<int> pq;

    // まずは目の前の料理を取(って回転から始めたい)
    int eaten=0;
    for(int i=0,m=1;i<n;i++,m<<=1) if (fav[i][i]) eaten |= m;
    int nt=(15<<20)|32768|eaten;
    pq.push(-nt);
    // 目の前の料理を取らない(で回転から始めたい)
    pq.push(-32768);
    
    while(!pq.empty()){
      int t=-pq.top(); pq.pop();
      if (found(s,t&0xfffff)) continue;

      int sc=t>>20, ofs=(t>>16)&15, eaten=t&0x7fff;
      s.insert(t&0xfffff);

      if (eaten == ful) return sc;

      if(t&32768){
        // 料理は取らず、[1..n-1]だけ回す
        rep(nofs,n){
          int d=nofs-ofs; if(d==0) continue;
          if(d<0)d=-d; if (n<d*2) d=n-d;
          int nt=((sc+1+d)<<20)|nofs*65536|eaten;
          pq.push(-nt);
        }
      } else {
        // 目の前の料理を取る
        for(int i=0,e=ofs,m=1;i<n;i++,e=(e+1)%n,m<<=1) if (fav[i][e]) eaten |= m;
        int nt=((sc+15)<<20)|ofs*65536|32768|eaten;
        pq.push(-nt);
      }
    }
    return -1;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090517