SRM 555 Div2 Medium CuttingBitString

問題

バイナリ文字列が与えられた時に,バイナリ文字列を分割する.その際,全ての分割で5のべき乗になるようにする.最少の分割回数を答える.なければ-1を返す.

解答

先頭から順番に5のべき乗になる最初の分割を求める.残りの文字列で同様に5のべき乗になるかを再帰的に計算.最少の分割数を答える.5のべき乗にならないと,再帰を行わないので,再帰数は十分に小さい(はず).

class CuttingBitString
{
public:
  int getmin(string S)
    {
      int res = 10000000;
      int i;
      int n = S.size();
      long long cur = 0;
      if (S[0] == '0') return -1;
      vector<long long> fives;
      long long v = 1;
      while(v < LONG_MAX/5){
        fives.push_back(v);
        v *= 5;
      }
      // cout << "*****************" << endl;
      for(i = 0; i < n; i++){
        if (S[i] == '1') cur += 1;
        // cout << "cur=" << cur << endl;
        bool isfivefactor = false;
        for(int i=0; i < fives.size(); i++) if (fives[i] == cur){
            isfivefactor = true;
            break;
          }
        if (isfivefactor) {
          if (i == (n-1)) return 1;
          string s2 = S.substr(i + 1);
          int s2v = getmin(s2);
          if (s2v > 0) res = min(res, 1 + s2v);
          // cur = cur << 1;
        }
        cur *= 2;
      }
      if (res == 10000000) return -1;
      return res;
    }
};