naoya_t@topcoder

SRM146 Div2 Hard: BridgeCrossing

過去問, 練習, Tutorials | 06:40 |

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にあるように、行きは２人（そもそも１人しかいない場合はその１人の所要時間が答え）で、帰りは向こう岸にいる中で一番早いのを返せばよいのでもう少し簡略化可能

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);
          // いちばん速いやつを１人戻せばよい
          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);
          // こちらからは２人行ったほうがよい。というか１人で行く理由はない
          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)

• いや、そんなに効率とか色々考えなくても
• ２人選んで行かせて、１人速いのを戻して、を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++のバックトラッキングか（気づくの遅すぎ）