SRM321Div2

250
苦労した。

class KDoubleSubstrings {
public:
  int howMuch(vector <string> str, int K) {
    int r = 0;
    string s;
    for(int i=0; i<str.size(); ++i){
      s += str[i];
    }
    for(int i=0; i<s.size(); ++i){
      for(int j=0; i+j<=s.size(); ++j){
        string t = s.substr(i, j);
        //cout << t << endl;
        if( t.size() % 2 )continue;
        string a, b;
        for(int k=0; k<t.size(); ++k){
          if(k < t.size() / 2)a += t[k];
          else b += t[k];
        }
        if(a.size() == 0)continue;
        if(b.size() == 0)continue;
        //cout << a << " : " << b << endl;
        int cnt = 0;
        for(int k=0; k<a.size(); ++k){
          cnt += a[k] != b[k];
        }
        r += cnt <= K;
      }           
    }
    return r;
  }
};

500
けっこう苦労した。

class Chocolate {
public:
  int minSplitNumber(int width, int height, int nTiles) {
    lli w = width;
    lli h = height;
    lli tile = nTiles;
    if( w * h == tile )return 0;
    if( w * h < tile )return -1;

    if( tile % w == 0 && tile / w <= h )return 1;
    if( tile % h == 0 && tile / h <= w )return 1;

    //lli mn = min(h, w); lli mx = max(h, w);
   
    for(lli i=1; i*i<=tile; ++i){
      if( tile % i )continue;
      lli j = tile / i;
      if(i < h && j < w)return 2;
      if(i < w && j < h)return 2;
    }

    return -1;
  }
};

1000

class LexStringWriter {
public:
  int minMoves(string s) {
    vector< pair<int, int> > v;
    string t;
    for(char c='a'; c<='z'; ++c){
      int left, right;
      left = s.find( c );
      right = s.rfind( c );
      if( left == string::npos || right == string::npos )continue;
      v.push_back( make_pair(left, right) );
      t += c;
    }
    
    const int inf = 1 << 21;
    const int size = t.size();
    int dp[size+1][2];
    fill( &dp[0][0], &dp[size][2], inf );

    const int L = 0;
    const int R = 1;

    dp[0][L] = v[0].second + abs( v[0].first - v[0].second );
    dp[0][R] = v[0].second;

    for(int i=1; i<t.size(); ++i){
      int a, b;

      int c = abs( v[i].first - v[i].second );

      a = abs( v[i].second - v[i-1].second ) + c;
      b = abs( v[i].second - v[i-1].first ) + c;
      dp[i][L] = min(b + dp[i-1][L], a + dp[i-1][R]);

      a = abs( v[i].first - v[i-1].second ) + c;
      b = abs( v[i].first - v[i-1].first ) + c;
      dp[i][R] = min(b + dp[i-1][L], a + dp[i-1][R]);
      
    }
  
    return min( dp[size-1][L], dp[size-1][R] ) + s.size();
  }
};