naoya_t@topcoder

SRM148 Div1 Medium: MNS

過去問, 練習, Tutorials | 23:07 |

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

Backtrackingで解く例（その２）。450点問題。

• C++のBacktrackingに慣れてきた
• 最初数字がぜんぜん合わないと思ったら３列目しかpermutationしてなかったorz
• Test Caseが４つ通ったので投げてみた
• 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);
  }
};