SRM572 Div1 Easy

250

前からの範囲と後ろからの範囲がオーバーラップすることに注意。
同じ文字にする必要のあるインデックスの中で、どれに合わせるべきかを調べていく。

class NewArenaPassword {
public:
  int minChange(string old, int K)
  {
    const int N = old.size();
    static int same[55];
    fill(same, same + N, -1);
    for (int i = 0; i < N; ++i) {
      int a = i;
      int b = N - K + i;
      same[max(a, b)] = min(a, b);
    }
    int ret = 0;
    for (int i = N - 1; 0 <= i; --i) {
      vector<int> v;
      for (int j = i; j != -1; j = same[j]) {
        v.push_back(j);
        if (j == same[j]) break;
      }
      char c = '@';
      int mx = 0;
      map<char, int> cnt;
      for (int j = 0; j < v.size(); ++j) {
        int m = ++cnt[old[v[j]]];
        if (mx < m) {
          mx = m;
          c = old[v[j]];
        }
      }
      if (c != '@') {
        for (int j = 0; j < v.size(); ++j) {
          if (old[v[j]] != c) {
            ++ret;
            old[v[j]] = c;
          }
        }
      }
    }
    return ret;
  }
};