1332 C. K-Complete Word

codeforces.com

問題概要

ある文字列SとKが与えられる。文字列SをK-completeな単語にするには最小で何文字変えれば良いか？なお、K-completeな単語とは以下のような単語を意味する。

• 回文である
• i文字目とi+K文字目が等しい

なお、t個のテストケースに対して回答する必要がある。

入出力

入力

4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

出力

2
0
23
16

解答

Union-Find木を使う。まず、等しくなければならない文字群を列挙し、この文字群のなかで最も出現率の高いものに揃える。このときがコスト最小となる。

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using vi = vector<int>;
template<class T>using vv = vector<vector<T>>;

#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0;i<(n);++i)

struct UnionFind {
  vector<int> parent;
  UnionFind(int n) {
    parent.resize(n, -1);
  }
  int root(int x) {
    if (parent[x] == -1)
      return x;
    return parent[x] = root(parent[x]);
  }
  void unite(int x, int y) {
    if (root(x) == root(y))
      return;
    x = root(x); y = root(y);
    parent[x] = y;
    return;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

int main() {
  int in(t);

  rep(i, t) {
    int in(N); int in(K);
    vector<char> S(N);
    UnionFind T(N);
    rep(j, N) cin >> S[j];
    // 等しくなければならない箇所をunite
    rep(j, N-K) T.unite(j, j+K);
    rep(j, N) T.unite(j, N-1-j);

    // それぞれの文字群で文字の出現回数をカウント
    vv<int> count(N, vi(26, 0));
    rep(j, N)
      ++count[T.root(j)][S[j]-'a'];

    set<int> s;
    int ans = 0;
    rep(j, N) {
      if (s.find(T.root(j)) != s.end())
        continue;
      s.insert(T.root(j));
      int max_count = 0, sum = 0;
      rep(k, 26) {
        max_count = max(max_count, count[T.root(j)][k]);
        sum += count[T.root(j)][k];
      }
      ans += sum - max_count;
    }
    cout << ans << endl;
  }

  return 0;
}