Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-23

SRM234 Div1 Medium: WeirdRocks

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

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

Backtrackingで解く例(その3)。650点問題。

  • とりあえず書いてみた
  • 問題文の4つのTest Caseは全部通る
  • 302.04points (42'45''), Failed System Test
  • 最大ケース(8行10列)で落ちる...というか帰って来ないし
#define rep_(var,n)  for(int var=-1;var<(n);var++)

string join(vector<string> strs, const string &delim="")
{
  int n=strs.size(); if (n==0) return "";
  stringstream ss;
  ss << strs[0];
  for(int i=1;i<n;i++) { ss << delim << strs[i]; }
  return ss.str();
}

class WeirdRooks {
 public:
  string describe(vector<int> cols) {
    set<pair<int,int> > ans;
    int R=sz(cols); //1-8
    int W=*max_element(all(cols));

    int M=0; rep(i,R) M+=cols[i];
    set<pair<int,vector<int> > > pat;
    int k=0;
    vector<int> m(W,-1);
    rep_(i0,cols[0]){
      if(i0>=0){
        k++; m[i0]=0;
      }
      if(R>=2) rep_(i1,cols[1]){
          if(i1>=0){
            if(m[i1]>=0) continue;
            k++; m[i1]=1;
          }
          if(R>=3) rep_(i2,cols[2]){
              if(i2>=0){
                if(m[i2]>=0) continue;
                k++; m[i2]=2;
              }
              if(R>=4) rep_(i3,cols[3]){
                  if(i3>=0){
                    if(m[i3]>=0) continue;
                    k++; m[i3]=3;
                  }
                  if(R>=5) rep_(i4,cols[4]){
                      if(i4>=0){
                        if(m[i4]>=0) continue;
                        k++; m[i4]=4;
                      }
                      if(R>=6) rep_(i5,cols[5]){
                          if(i5>=0){
                            if(m[i5]>=0) continue;
                            k++; m[i5]=5;
                          }
                          if(R>=7) rep_(i6,cols[6]){
                              if(i6>=0){
                                if(m[i6]>=0) continue;
                                k++; m[i6]=6;
                              }
                              if(R==8) rep_(i7,cols[7]){
                                  if(i7>=0){
                                    if(m[i7]>=0) continue;
                                    k++; m[i7]=7;
                                  }
                                  if(R==8) pat.insert(make_pair(k,m));
                                  if(i7>=0){ k--; m[i7]=-1; }
                                }//7
                              if(R==7) pat.insert(make_pair(k,m));
                              if(i6>=0){ k--; m[i6]=-1; }
                            }//6
                          if (R==6) pat.insert(make_pair(k,m));
                          if(i5>=0){ k--; m[i5]=-1; }
                        }//5
                      if (R==5) pat.insert(make_pair(k,m));
                      if(i4>=0){ k--; m[i4]=-1; }
                    }//4
                  if (R==4) pat.insert(make_pair(k,m));
                  if(i3>=0){ k--; m[i3]=-1; }
                }//3
              if (R==3) pat.insert(make_pair(k,m));
              if(i2>=0){ k--; m[i2]=-1; }
            }//2
          if (R==2) pat.insert(make_pair(k,m));
          if(i1>=0){ k--; m[i1]=-1; }
        }//1
      if (R==1) pat.insert(make_pair(k,m));
      if(i0>=0){ k--; m[i0]=-1; }
    }//0

    tr(pat,it){
      int k=it->first;
      vector<int> m=it->second;
      vector<vector<bool> > sp(R,vector<bool>(W,false));
      rep(r,R) rep(c,cols[r]) sp[r][c]=true;
      rep(c,W){
        if(m[c]>=0) { // (c,m[i])
          int r=m[c];
          for(int j=0;j<=c;j++) sp[r][j]=false;
          for(int j=0;j<=r;j++) sp[j][c]=false;
        }
      }
      int sc=0;
      rep(r,R) rep(c,cols[r]) if(sp[r][c])sc++;
      ans.insert(make_pair(k,sc));
    }
    
    vector<string> vs;
    tr(ans,it){
      char buf[6]; sprintf(buf,"%d,%d",it->first,it->second); vs.pb(buf);
    }
    return join(vs," ");
  }
};
  • なんとかしたい。とりあえずパターンをlong longにしてみる
class WeirdRooks {
 public:
  string describe(vector<int> cols) {
    set<pair<int,int> > ans;
    int R=sz(cols); //1-8
    int W=*max_element(all(cols));

    int M=0; rep(i,R) M+=cols[i];
    set<ll> pat;
    int k=0;
    ll m=0LL;
    vector<ll> m_(8,0LL);
    rep_(i0,cols[0]){
      if(i0>=0){
        m_[0] = m;
        m |= (1LL << (4*i0));
      }
      if(R>=2) rep_(i1,cols[1]){
          if(i1>=0){
            if(m & (15LL <<(4*i1))) continue;
            m_[1] = m;
            m |= (2LL << (4*i1));
          }
          if(R>=3) rep_(i2,cols[2]){
              if(i2>=0){
                if(m & (15LL <<(4*i2))) continue;
                m_[2] = m;
                m |= (3LL << (4*i2));
              }
              if(R>=4) rep_(i3,cols[3]){
                  if(i3>=0){
                    if(m & (15LL <<(4*i3))) continue;
                    m_[3] = m;
                    m |= (4LL << (4*i3));
                  }
                  if(R>=5) rep_(i4,cols[4]){
                      if(i4>=0){
                        if(m & (15LL <<(4*i4))) continue;
                        m_[4] = m;
                        m |= (5LL << (4*i4));
                      }
                      if(R>=6) rep_(i5,cols[5]){
                          if(i5>=0){
                            if(m & (15LL <<(4*i5))) continue;
                            m_[5] = m;
                            m |= (6LL << (4*i5));
                          }
                          if(R>=7) rep_(i6,cols[6]){
                              if(i6>=0){
                                if(m & (15LL <<(4*i6))) continue;
                                m_[6] = m;
                                m |= (7LL << (4*i6));
                              }
                              if(R==8) rep_(i7,cols[7]){
                                  if(i7>=0){
                                    if(m & (15LL <<(4*i7))) continue;
                                    m_[7] = m;
                                    m |= (8LL << (4*i7));
                                  }
                                  if(R==8) pat.insert(m);
                                  if(i7>=0) m=m_[7];
                                }//7
                              if(R==7) pat.insert(m);
                              if(i6>=0) m=m_[6];
                            }//6
                          if (R==6) pat.insert(m);
                          if(i5>=0) m=m_[5];
                        }//5
                      if (R==5) pat.insert(m);
                      if(i4>=0) m=m_[4];
                    }//4
                  if (R==4) pat.insert(m);
                  if(i3>=0) m=m_[3];
                }//3
              if (R==3) pat.insert(m);
              if(i2>=0) m=m_[2];
            }//2
          if (R==2) pat.insert(m);
          if(i1>=0) m=m_[1];
        }//1
      if (R==1) pat.insert(m);
      if(i0>=0) m=m_[0];
    }//0

    // cout << "pat.size = " << sz(pat) << endl;
    {
      vector<int> m(W,-1);
      vector<vector<bool> > sp(R,vector<bool>(W,false));
      int k=0;
      tr(pat,it){
        rep(i,W) m[i]=(((*it) >> (4*i)) & 15)-1;
        rep(r,R) rep(c,cols[r]) sp[r][c]=true;
        k=0;
        rep(c,W){
          if(m[c]>=0) { // (c,m[i])
            k++;
            int r=m[c];
            for(int j=0;j<=c;j++) sp[r][j]=false;
            for(int j=0;j<=r;j++) sp[j][c]=false;
          }
        }
        int sc=0;
        rep(r,R) rep(c,cols[r]) if(sp[r][c])sc++;
        ans.insert(make_pair(k,sc));
      }
    }
    
    vector<string> vs;
    tr(ans,it){
      char buf[6]; sprintf(buf,"%d,%d",it->first,it->second); vs.pb(buf);
    }
    return join(vs," ");
  }
};

最大ケースでも帰ってくるようになったが1分前後かかる。12975561パターンあるのでこんなのでは駄目かと。(とりあえずここまで)

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090523

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);
  }
};

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

2009-05-20

vectorで多次元配列を作る場合の初期化

| 02:19 | vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder を含むブックマーク はてなブックマーク - vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder vectorで多次元配列を作る場合の初期化 - naoya_t@topcoder のブックマークコメント

Multidimensional arrays are very important. The simplest way to create the two-dimensional array via vector is to create a vector of vectors.

vector< vector<int> > Matrix; 

It should be clear to you now how to create the two-dimensional vector of given size:

int N, M; 
// ... 
vector< vector<int> > Matrix(N, vector<int>(M, -1)); 

Here we create a matrix of size N*M and fill it with -1.

Power up C++ with the Standard Template Library: Part I - Algorithm Tutorials

知らなかった...

Abusing C++ Extensions for Fun and Profit

| 02:41 | Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder を含むブックマーク はてなブックマーク - Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder Abusing C++ Extensions for Fun and Profit - naoya_t@topcoder のブックマークコメント

http://www.topcoder.com/tc?module=Static&d1=features&d2=022006

Compound literals

I often define a small struct that will hold two or three items, such as the end-points and weight of an edge in a graph. For two-item structs there is already the utility pair template, but it has unfriendly field names (first and second compared to, say, target and cost), and it doesn't generalise well to more than two elements (although you can create a pair<pair<R, S>, T> if you really insist).


One advantage of pair that you lose when you do this is the make_pair function that creates pairs on the fly. You could of course define such a function for your class, or give it a constructor, but this can take vital coding time. GCC provides another alternative, which comes from C99: the compound literal. A compound literal is a mix between a cast and an initialiser. To understand what I mean, consider a struct defined as

struct edge
{
    int target;
    int cost;
};

An example of a compound literal is (edge) { t, c } where t and c are expressions. The values in the braces are used to initialise the values of the struct, in the order in which they are declared. This is useful for instantiating structs on-the-fly to pass to STL methods.

Comparisons

Although the header <algorithm> provides min and max functions, these have some limitations. They have only one template parameter, which specifies the type for both arguments; this sometimes leads to errors when the given arguments are of different types. GCC provides the highly non-standard operators ? (max), which will coerce the arguments to a suitable type.


These operators are most commonly seen in their assignment forms ?=. For example, the following loop computes the minimum value of a function over a range:

int m = INT_MAX;
for (int i = 0; i < N; i++)
    m <?= func(i);

これは見たことある

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090520

2009-05-19

SRM211 Div1 Medium: grafixMask

| 00:28 | SRM211 Div1 Medium: grafixMask - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM211 Div1 Medium: grafixMask - naoya_t@topcoder SRM211 Div1 Medium: grafixMask - naoya_t@topcoder のブックマークコメント

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

  • 問題がなかなか頭に入らなかった
  • ニコ動をBGMにしながらは無理か
  • いつもpriority_queue使うけど今日は普通のqueueで。合理的に使い分けているわけではない
  • 214.27points (50'0''), passed system test
#define RC 240000
class grafixMask {
 public:
  vector<int> sortedAreas(vector<string> rectangles) {
    vector<int> wh(RC,0); // r*600+c
    int rem=RC;
    tr(rectangles,it){
      vector<int> rs = map_atoi(split(*it));
      for(int r=rs[0]; r<=rs[2]; r++){
        for(int c=rs[1]; c<=rs[3]; c++){
          int rc=r*600 + c;
          if(wh[rc]==0){ wh[rc]=-1; rem--; }
        }
      }
    }

    vector<int> ans;
    int room=1;
    while(rem){
      // find emptypoint
      int erc=-1;
      rep(rc,RC) if (wh[rc]==0){ erc=rc; goto found; }
      if (erc==-1) goto err;
   found:
      // flood fill
      queue<int> q;
      vector<bool> vac(RC,false);
      rep(rc,RC) if(wh[rc]==0) vac[rc]=true;
      q.push(erc); vac[erc]=false;
      while(!q.empty()){
        int rc=q.front(); q.pop();
        if(wh[rc]==0){ wh[rc]=room; rem--; }
        int r=rc/600, c=rc%600;
        if(1<=r && vac[rc-600]){ q.push(rc-600); vac[rc-600]=false;}
        if(r<=398 && vac[rc+600]){ q.push(rc+600); vac[rc+600]=false;}
        if(1<=c && vac[rc-1]){ q.push(rc-1); vac[rc-1]=false;}
        if(c<=598 && vac[rc+1]){ q.push(rc+1); vac[rc+1]=false;}
      }
      room++;
    }
    ans.resize(room-1); rep(i,room-1) ans[i]=0;
    rep(rc,RC){
      if (wh[rc]>0) ans[wh[rc]-1]++;
    }
    sort(all(ans));
 err:
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090519

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;
  }
};

SRM222 Div1 Medium: WalkingHome

| 18:40 | SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder のブックマークコメント

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

  • BFSの例
  • そんなに難しくない
  • 最初のsubmit: 262.33points (34'29'')
  • 南北の道を横断している途中に東西の道を縦断できてしまうバグでfailed
  • 直したはず (#2のところ) が直ってなくてfailed
  • 1つ外のifで分岐させてやっと直った。
    • 横断している道から横にそれたら斜め横断になってしまうということ
  • 教訓:きちんと場合分けしてテストしよう
#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())

class WalkingHome {
 public:
  int fewestCrossings(vector <string> m) {
    int w=sz(m[0]),h=sz(m);
    int start_x=-1, start_y=-1, goal_x=-1, goal_y=-1;
    vector<vector<bool> > fu(h);
    rep(y,h) { fu[y].resize(w); rep(x,w) fu[y][x]=true; }
    rep(y,h) rep(x,w) {
      switch(m[y][x]){
        case 'S': start_x=x; start_y=y; break;
        case 'H': goal_x=x; goal_y=y; break;
        case '*':
        case 'F': fu[y][x] = false; break;
        case '|': case '-':
        case '.':
          break;
      }
    }
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push(make_pair(0,make_pair(start_x,start_y)));
    while(!pq.empty()){
      int sc=-pq.top().first;
      int x=pq.top().second.first, y=pq.top().second.second;
      if (x==goal_x && y==goal_y) return sc;
      pq.pop();
      if(fu[y][x]){
        int cur = m[y][x];
        if (0<=x-1 && cur!='-') { // <
          if (fu[y][x-1]) {
            int nxt=m[y][x-1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x-1,y)));
                break;
            }
          }
        }
        if (x+1<=w-1 && cur!='-') { // >
          if (fu[y][x+1]) {
            int nxt=m[y][x+1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x+1,y)));
                break;
            }
          }
        }
        
        if (0<=y-1 && cur!='|') { // ^
          if (fu[y-1][x]) {
            int nxt=m[y-1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y-1)));
                break;
            }
          }
        }
        if (y+1<=h-1 && cur!='|') { // v
          if (fu[y+1][x]) {
            int nxt=m[y+1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y+1)));
                break;
            }
          }
        }
      }
      fu[y][x] = false;
    }
    return -1;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090517