Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 433 Div1 Easy 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695:title=SRM 433 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10195&rd=13695:title=SRM 433 Div1 Easy] - shnyaの参戦記録

next_permutationが重複するものに使えないとばかり思っていて自分で再帰使って書きました。

でも実際は、インデックスを保存したvector<int>を使ってnext_permutationを使えばいいということを指摘されて、

なぜ思いつかなかったし、と凹む。


class MagicWords
{
  void permute0(size_t i, vector<int> &used, vector<int> &path, const vector<int> &v, vector<vector<int> > &result){
    if(i == v.size()){
      result.push_back(path);
      return;
    }
    for(int j = 0; j < int(v.size()); j++){
      if(used[j] != 1){
        used[j] = 1;
        path.push_back(v[j]);
        permute0(i+1,used,path,v,result);
        path.pop_back();
        used[j] = 0;
      }
    }
  }

  void permute(const vector<int> &v, vector<vector<int> > &result){
    vector<int> path, used(v.size());
    permute0(0,used,path,v,result);
  }

public:
  int count(vector <string> S, int K)
  {
    vector<vector<int> > result;
    vector<int> v(S.size());
    for(int i = 0; i < int(S.size()); ++i){
      v[i] = i;
    }
    permute(v,result);
    //debug(result);
    int res = 0;
    for(int i = 0; i < int(result.size()); ++i){
      vector<int> &vv = result[i];
      string s;
      for(int j = 0; j < int(vv.size()); ++j){
        s += S[vv[j]];
      }
      if(int(s.size()) % K != 0) return 0;
      int siz = s.size();
      for(int j = 1; j <= siz/ K; ++j){
        if(siz % j != 0) continue;
        string res2 = s.substr(0,j);
        for(int k = 1; k < int(s.size())/j; ++k){
          if(res2 != s.substr(j*k,j)){
            goto fail;
          }
        }
        if(j == int(s.size())/K){
          res++;
          break;
        }else{
          goto fail2;
        }
      fail:;
      }
    fail2:;
    }
    return res;
  }