Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-22

SRM148 Div1 Medium: MNS

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

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

Backtrackingで解く例(その2)。450点問題。

  • C++のBacktrackingに慣れてきた
  • 最初数字がぜんぜん合わないと思ったら3列目しかpermutationしてなかったorz
  • Test Caseが4つ通ったので投げてみた
  • 325.10points (19'13''), Passed system test
  • わーい
class MNS {
 public:
  int combos(vector<int> ns) {
    set<vector<int> > ans;
    int sum=0;
    rep(i,9) sum+=ns[i];
    if(sum%3) return 0;
    sort(all(ns));
    int rowsum=sum/3;
    for(int i=0;i<7;i++){
      for(int j=i+1;j<8;j++){
        for(int k=j+1;k<9;k++){
          vector<int> as(3); as[0]=ns[i]; as[1]=ns[j]; as[2]=ns[k];
          if (as[0]+as[1]+as[2] == rowsum) {
            ns.erase(ns.begin()+k);
            ns.erase(ns.begin()+j);
            ns.erase(ns.begin()+i);
            for(int u=0;u<4;u++){
              for(int v=u+1;v<5;v++){
                for(int w=v+1;w<6;w++){
                  vector<int> bs(3); bs[0]=ns[u]; bs[1]=ns[v]; bs[2]=ns[w];
                  if (bs[0]+bs[1]+bs[2] == rowsum) {
                    ns.erase(ns.begin()+w);
                    ns.erase(ns.begin()+v);
                    ns.erase(ns.begin()+u);

                    do {
                      do {
                        do {
                          if ( (as[0]+bs[0]+ns[0] == rowsum)
                               && (as[1]+bs[1]+ns[1] == rowsum)
                               && (as[2]+bs[2]+ns[2] == rowsum) ) {
                            int a_[9] = { as[0],as[1],as[2], bs[0],bs[1],bs[2], ns[0],ns[1],ns[2] };
                            vector<int> a(a_, a_+sizeof(a_)/sizeof(*a_));
                            ans.insert(a);
                          }
                        } while (next_permutation(all(ns)));
                      } while (next_permutation(all(bs)));
                    } while (next_permutation(all(as)));

                    ns.pb(bs[0]); ns.pb(bs[1]); ns.pb(bs[2]);
                    sort(all(ns));
                  }
                }
              }
            }
            ns.pb(as[0]); ns.pb(as[1]); ns.pb(as[2]);
            sort(all(ns));
          }
        }
      }
    }
    return sz(ans);
  }
};

SRM148 Div1 Easy: CircleGame

| 22:44 | SRM148 Div1 Easy: CircleGame - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM148 Div1 Easy: CircleGame - naoya_t@topcoder SRM148 Div1 Easy: CircleGame - naoya_t@topcoder のブックマークコメント

  • やるだけ
  • なのにeraseで迷う
  • 213.37 (12'12''), passed system test
  • 遅いっす
class CircleGame {
 public:
  int cardsLeft(string deck) {
    vector<int> dk;
    rep(i,sz(deck)){
      switch(deck[i]){
        case 'K': break;
        case 'A': dk.pb(1); break;
        case 'T': dk.pb(10); break;
        case 'J': dk.pb(11); break;
        case 'Q': dk.pb(12); break;
        default: dk.pb(deck[i]-'0'); break;
      }
    }
    int l=sz(dk),ll=l+1;
    while(l<ll){
      rep(i,l){
        if(dk[i]+dk[(i+1)%l]==13) {
          if (i+1==l) {
            dk.erase(dk.begin()+i);
            dk.erase(dk.begin());
            break;
          } else {
            dk.erase(dk.begin()+i+1);
            dk.erase(dk.begin()+i);
            break;
          }
        }
      }
      ll=l;
      l=sz(dk);
    }
    return l;
  }
};

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++のバックトラッキングか(気づくの遅すぎ)

SRM232 Div1 Easy: WordFind

| 05:11 | SRM232 Div1 Easy: WordFind - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM232 Div1 Easy: WordFind - naoya_t@topcoder SRM232 Div1 Easy: WordFind - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その4)。

  • 223.81points →縦・横・斜めのうち最初に見つけたやつを返してたのでfailed system test
  • 縦・横・斜めまでちゃんと調べてからソート。passed system test
  • 問題文の例が通ったからと言って油断しないこと
class WordFind {
  string str(int y, int x){
    stringstream ss;
    ss << y << " " << x;
    return ss.str();
  }
 public:
  vector <string> findWords(vector <string> grid, vector <string> wordList) {
    int gw=sz(grid[0]),gh=sz(grid);
    int n=sz(wordList);
    vs ans(n,"");
    rep(i,n){
      vector<pair<int,int> > buf;
      string w=wordList[i]; char w0=w[0]; int l=sz(w);
      // yoko
      for(int y=0;y<gh;y++){
        for(int x=0;x<=gw-l;x++){
          if(grid[y][x]!=w0) goto fail1;
          for(int z=1;z<l;z++){
            if(grid[y][x+z]!=w[z]) goto fail1;
          }
          buf.pb(make_pair(y,x));
          goto cont1; 
       fail1:;
        }
      }
   cont1:
      // tate
      for(int y=0;y<=gh-l;y++){
        for(int x=0;x<gw;x++){
          if(grid[y][x]!=w0) goto fail2;
          for(int z=1;z<l;z++){
            if(grid[y+z][x]!=w[z]) goto fail2;
          }
          buf.pb(make_pair(y,x));
          goto cont2;
       fail2:;
        }
      }
   cont2:
      // naname
      for(int y=0;y<=gh-l;y++){
        for(int x=0;x<=gw-l;x++){
          if(grid[y][x]!=w0) goto fail3;
          for(int z=1;z<l;z++){
            if(grid[y+z][x+z]!=w[z]) goto fail3;
          }
          buf.pb(make_pair(y,x));
          goto cont3;
       fail3:;
        }
      }
   cont3:
      sort(all(buf));
      if (sz(buf) > 0) ans[i] = str(buf[0].first, buf[0].second);
    }
    return ans;
  }
};

SRM229 Div1 Easy: Cafeteria

| 04:51 | SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder SRM229 Div1 Easy: Cafeteria - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その3)。

  • 数があわないと思ったら、いちばん速いバス停を求めていたorz
  • 直した
  • 210.60points (12'47''), Passed System Test
  • なんか遅いなあ>自分
class Cafeteria {
  string twelve(int min){
    int h=min/60, m=min%60;
    if (h>12) h-=12;
    char buf[6];
    sprintf(buf,"%02d:%02d",h,m);
    return buf;
  }
 public:
  string latestTime(vector <int> offset, vector <int> walkingTime, vector <int> drivingTime) {
    int n=sz(offset);
    int lim=60*14+30;
    int latest=0;
    rep(i,n){
      int o=offset[i],// 0-9
          wt=walkingTime[i],//1-30
          dt=drivingTime[i];//1-300
      int lastdep=lim-dt, lastdepo=lastdep%10, lastdep0 = lastdep-lastdepo;
      int busdep= (o<=lastdepo)? (lastdep0+o) : (lastdep0-10+o);
      int dep=busdep-wt;
      latest >?= dep;
    }
    return twelve(latest);
  }
};

SRM212 Div2 Hard: LargestCircle

| 04:27 | SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その2)。

  • とりうる中心&半径について全て試してみた
  • 普通にコンパイルするとTest Case #6で2.6秒かかったが、-O3 で161msec。余裕
  • 718.97points (19'25''), Passed System Test
class LargestCircle {
  int in(int x,int y,int r, int u,int v){
    return (u-x)*(u-x) + (v-y)*(v-y) - r*r;
  }
 public:
  int radius(vector<string> grid) {
    int h=sz(grid), w=sz(grid[0]);
    if (h==1 || w==1) return 0;
    int R = 0;
    for(int x=1;x<=w-1;x++){
      int dxmax=min(x,w-x);
      for(int y=1;y<=h-1;y++){
        int dymax=min(y,h-y);
        int rmax=min(dxmax,dymax);
        for(int r=rmax;r>=1;r--){
          bool ok=true;
          for(int u=0;u<w;u++){
            for(int v=0;v<h;v++){
              if(grid[v][u]=='#'){
                int a = in(x,y,r, u,v);
                int b = in(x,y,r, u+1,v);
                int c = in(x,y,r, u,v+1);
                int d = in(x,y,r, u+1,v+1);
                if ((a>=0 && b>=0 && c>=0 && d>=0) || (a<=0 && b<=0 && c<=0 && d<=0)) {
                } else {
                  ok=false; goto out;
                }
              }
            }
          }
       out:
          if (ok) R>?=r; // ←コンパイル時にwarning出るね
        }
      }
    }
    return R;
  }
};
  • >?= なのか <?= なのかぱっと分からないので両方試したのは内緒。
  • コンパイル時にwarning出るが構わない

LargestCircle.cpp: In member function ‘int LargestCircle::radius(std::vector<std::string, std::allocator<std::string> >)’:

LargestCircle.cpp:75: warning: minimum/maximum operators are deprecated

SRM197 Div1 Easy: GeneralChess

| 02:59 | SRM197 Div1 Easy: GeneralChess - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM197 Div1 Easy: GeneralChess - naoya_t@topcoder SRM197 Div1 Easy: GeneralChess - naoya_t@topcoder のブックマークコメント

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

  • まあやるだけですが
  • knightの動ける位置とかコピペで行けるようにしておくべきだ
  • 197.98points (15'25'') 時間かけすぎ
  • Passed System Test
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<int,int> ii;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

// split(), map_atoi() は自作

int knight[8][2] = { {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1} };

class GeneralChess {
 public:
  vector <string> attackPositions(vector <string> pieces) {
    int n=sz(pieces);
    map<ii,int> m;
    rep(i,n){
      vi xy = map_atoi(split(pieces[i],','));
      rep(j,8){
        ii xy_ = make_pair(xy[0] + knight[j][0],
                           xy[1] + knight[j][1]);
        if (found(m,xy_)) m[xy_]++;
        else m[xy_]=1;
      }
    }
    vector<ii> v;
    tr(m,it){
      if(it->second==n) v.pb(it->first);
    }
    sort(all(v));
    vector<string> ans;
    tr(v,it){
      char buf[14];
      sprintf(buf,"%d,%d", it->first, it->second);
      ans.pb(buf);
    }
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090522