SRM551 Div2 Medium

500

使う文字と範囲を全部試す。

class ColorfulChocolates {
public:
  int maximumSpread(string C, int S)
  {
    const int N = C.size();

    map< char, vector<int> > index;
    for (int i = 0; i < N; ++i) {
      index[C[i]].push_back(i);
    }

    int mx = 1;

    for (int begin = 0; begin < N; ++begin) {
      for (int len = 1; begin + len <= N; ++len) {
        for (char c = 'A'; c <= 'Z'; ++c) {
          vector<int> v = index[c];
          if (len <= v.size()) ; else continue;
          for (int i = 0; i + len <= v.size(); ++i) {
            int cost = 0;
            for (int j = 0; j < len; ++j) {
              int src = v[i + j];
              int dst = begin + j;
              cost += abs(src - dst);
            }
            if (cost <= S) mx = max(mx, len);
          }
        }
      }
    }

    return mx;
  }
};