naoya_t@topcoder

SRM360 Div1 Easy: SumOfSelectedCells

過去問, 練習 | 00:21 |

これは難しい。むしろ撃墜レースと考えるべき問題。実際Div1でも通過率34%と、500点問題を下回っている。

• DP的に解こうとしている
• 数回のsubmit/systestの末、とりあえず以下のコードまで来た
• まだCase#37がTLE
• 後で上手な人のコードを見るとしよう

class SumOfSelectedCells {
 public:
  string hypothesis(vector<string> table) {
    int h=sz(table);
    vector<vector<int> > t(h);
    rep(i,h) t[i]=map_atoi(split(table[i]));
    int w=sz(t[0]);
    if(w>h){
      vector<vector<int> > t_(w);
      rep(i,w) t_[i].resize(h);
      rep(i,w) rep(j,h) t_[i][j]=t[j][i];
      t=t_;
      swap(w,h);
    }
    // w<=h

    map<int,int> memo;
    int mmax=1<<h;

    if(w==1){
      int z=t[0][0];
      for(int i=1;i<h;i++) if(z!=t[i][0]) goto incorrect;
      goto correct; //oops
    }
    if(h==2){
      if (t[0][0]+t[1][1] == t[1][0]+t[0][1])
        goto correct;
      else
        goto incorrect;
    }
    // nC2
    rep(x,h) {
      rep(i,h) {
        if(i==x) continue;
        rep(j,h) {
          if(j==x||i>=j) continue; //j>i
          int s_ij=t[i][0]+t[j][1],
              s_ji=t[j][0]+t[i][1];
          if(s_ij!=s_ji) goto incorrect;
          int m=(1<<i)|(1<<j);
          memo[m|(2<<h)]=s_ij;
        }
      }
    }
    if(w==2){
      if(h>w){
        int s=-1;
        tr(memo,it){
          int s_=it->second;
          if(s<0)s=s_;
          else if(s!=s_) goto incorrect;
        }
      }
      goto correct;
    }

    for(int d=3;d<=w;d++){
      int b=d+(h-w);
      rep(m,mmax){
        if(__builtin_popcount(m)!=b) continue;
        int s=-1;
        rep(i,h){
          int x=1<<i;
          if((m&x)==0) continue;
          int m_=m-x;
          if(d==3 && b>3){
            for(int m2=3;m2<mmax;m2++){
              if(__builtin_popcount(m2)!=2) continue;
              if((m_&m2)==m2){ m_=m2; break; }
            }
          }
          int s_=t[i][d-1]+memo[m_|((d-1)<<h)];
          if(s<0) s=s_;
          else if(s!=s_) goto incorrect;
        }
        memo[m|(d<<h)]=s;
      }
    }

 correct:
    return "CORRECT";
 incorrect:
    return "INCORRECT";
  }
};