naoya_t@topcoder

SRM219 Div1 Medium: TurntableService

過去問, 練習, Tutorials | 23:03 |

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:各人が好物を既に１つ以上食べているか(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;
  }
};