naoya_t@topcoder

SRM234 Div1 Medium: WeirdRocks

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

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

Backtrackingで解く例（その３）。650点問題。

• とりあえず書いてみた
• 問題文の４つの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," ");
  }
};

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