Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-22

SRM146 Div2 Hard: BridgeCrossing

| 06:40 | SRM146 Div2 Hard: BridgeCrossing - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM146 Div2 Hard: BridgeCrossing - naoya_t@topcoder SRM146 Div2 Hard: BridgeCrossing - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Backtrackingで解く例。

  • backtrackingってC++でどう書けばよいのか
  • call/ccとかじゃなくて
  • ...
  • とりあえず解いてみる
  • 672.98points (22'12''), passed system test
class BridgeCrossing {
 public:
  int minTime(vector <int> times) {
    int m=sz(times);
    int fl=(1<<(m+1))-1;
    int lt=1<<m;
    vector<int> tm(lt);
    rep(i,lt){
      int t=0;
      for(int j=0,k=1;j<m;j++,k<<=1){
        if(i & k) t >?= times[j];
      }
      tm[i] = t;
    }
    
    priority_queue<ii> pq;
    pq.push(make_pair(0,0));
    vector<int> d(fl+1,INT_MAX); d[0]=0;
    while(!pq.empty()){
      ii t=pq.top(); pq.pop();
      int sc=-t.first, z=t.second;
      if(z==fl) return sc;
      if(z & lt){
        // あっちから
        for(int i=1;i<lt;i++){
          if((i&z) < i) continue;
          int popc=__builtin_popcount(i);
          if(popc==1 || popc==2){
            int newz=z-lt-i;
            int newsc=sc+tm[i];
            if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
          }
        }
      } else {
        // こっちから
        for(int i=1;i<lt;i++){
          if((i&z) > 0) continue;
          int popc=__builtin_popcount(i);
          if(popc==1 || popc==2){
            int newz=z+lt+i;
            int newsc=sc+tm[i];
            if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
          }
        }
      }
    }
    return -1;
  }
};

Test Case #0...PASSED (0.377 msec)

Test Case #1...PASSED (0.19 msec)

Test Case #2...PASSED (0.021 msec)

Test Case #3...PASSED (0.46 msec)

  • Tutorialにあるように、行きは2人(そもそも1人しかいない場合はその1人の所要時間が答え)で、帰りは向こう岸にいる中で一番早いのを返せばよいのでもう少し簡略化可能
typedef pair<int,int> ii;

class BridgeCrossing {
 public:
  int minTime(vector <int> times) {
    int m=sz(times);
    if (m==1) return times[0]; // 1人ならそいつの所要時間が答え
    
    sort(all(times));
    int fl=(1<<(m+1))-1;
    int lt=1<<m;
    vector<int> tm(lt);
    rep(i,lt){
      int t=0;
      for(int j=0,k=1;j<m;j++,k<<=1){
        if(i & k) t >?= times[j];
      }
      tm[i] = t;
    }
    
    priority_queue<ii> pq;
    pq.push(make_pair(0,0));
    vector<int> d(fl+1,INT_MAX); d[0]=0;
    while(!pq.empty()){
      ii t=pq.top(); pq.pop();
      int sc=-t.first, z=t.second;
      if(z==fl) return sc;
      if(z & lt){
        // あっちから
        for(int i=1;i<lt;i++){
          if((i&z) < i) continue;
          int popc=__builtin_popcount(i);
          // いちばん速いやつを1人戻せばよい
          if(popc==1){
            int newz=z-lt-i;
            int newsc=sc+tm[i];
            if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
            break;
          }
        }
      } else {
        // こっちから
        for(int i=1;i<lt;i++){
          if((i&z) > 0) continue;
          int popc=__builtin_popcount(i);
          // こちらからは2人行ったほうがよい。というか1人で行く理由はない
          if(popc==2){
            int newz=z+lt+i;
            int newsc=sc+tm[i];
            if(d[newz]>newsc){ d[newz]=newsc; pq.push(make_pair(-newsc,newz)); }
          }
        }
      }
    }
    return -1;
  }
};

Test Case #0...PASSED (0.314 msec)

Test Case #1...PASSED (0.096 msec)

Test Case #2...PASSED (0.005 msec)

Test Case #3...PASSED (0.192 msec)

  • いや、そんなに効率とか色々考えなくても
  • 2人選んで行かせて、1人速いのを戻して、をvectorのままナイーブに実装したって余裕で間に合う。
  • Div1だと多分そのままではTLEな問題に加工されて出る
class BridgeCrossing {
  int sub(vector<int> &here, vector<int> &there, int cur){
    int l=sz(here);
    priority_queue<int> pq;
    for(int i=0;i<l-1;i++){
      for(int j=i+1;j<l;j++){
        int a=here[i], b=here[j];
        // >(a,b)>
        remove_(here,a); there.pb(a);
        remove_(here,b); there.pb(b);
        if(l==2) {
          pq.push(-(cur+max(a,b)));
        } else {
          sort(all(there));
          int c=there[0];
          // <c<
          remove_(there,c); here.pb(c);
          sort(all(here)); sort(all(there));
          pq.push(-sub(here,there,cur+max(a,b)+c));
          // backtracking: >c>
          remove_(here,c); there.pb(c);
        }
        // backtracking: <(a,b)<
        remove_(there,a); here.pb(a);
        remove_(there,b); here.pb(b);
        sort(all(here)); sort(all(there));
      }
    }
    return -pq.top();
  }
 public:
  int minTime(vector <int> times) {
    int m=sz(times);
    if (m==1) return times[0];

    vector<int> here(all(times)), there;
    return sub(here,there,0);
  }
};

Test Case #0...PASSED (0.376 msec)

Test Case #1...PASSED (1.717 msec)

Test Case #2...PASSED (0.004 msec)

Test Case #3...PASSED (26.03 msec)

  • ああ、こういう風に変更を元に戻すコードを自分で書いて次に進むスタイルは見た事がある
  • これがC++のバックトラッキングか(気づくの遅すぎ)
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090522