E - Level K Palindrome - 第二回日本最強プログラマー学生選手権

E - Level K Palindrome

• 回文のレベルを以下のように定める（正確には問題ページ参照）
  • 'a' や 'b' はレベル1の回文
  • 'aa' や 'aba' はレベル2の回文
  • '(レベル $L$ の回文)(レベル $L$ の回文)' という回文はレベル $L+1$
  • '(レベル $L$ の回文)(任意の1文字)(レベル $L$ の回文)' という回文もレベル $L+1$
• 文字列 $S$ と整数 $K$ が与えられる
• $S$ を、いくつかの文字を書き換えることでちょうどレベル $K$ の文字列にできるか判定し、できる場合は書き換える必要のある最小の文字数を求めよ
• $0 \le K \le 5 \times 10^5$
• $1 \le |S| \le 5 \times 10^5$

レベル1の回文で同じにならないといけない文字を考えると、以下のようになる。

|S| = 18 とすると、同じ高さになったindexの文字は同じである必要がある

0                                                 17
   1                                           16
      2                                     15
         3                               14
            4                         13
               5                   12
                  6             11
                     7       10
                        8  9

レベル2の回文では、さらに以下の文字が同じである必要がある。

0                       8  9                      17
   1                 7       10                16
      2           6             11          15
         3     5                   12    14
            4                         13

レベル3では

0        3     5        8  9       12    14       17
   1  2           6  7       10 11          15 16
            4                         13

レベル4……と思いきや、これはレベル5

0  1  2  3     5  6  7  8  9 10 11 12    14 15 16 17
            4                         13

各表現は、最初の折り返し直前までの文字列（レベル1なら 012345678、レベル2なら 0123、レベル3なら 01）がレベル0である（回文でない）ことを前提としているが、 レベル4のように折り返し直前までの文字列が1文字だけになったら、これはレベル1の文字列となってしまう。

よってその場合のみ、レベルが1ずれる。レベル4の文字列は作るのが不可能となる。またレベル6以上も長さ18の $S$ では作るのが不可能とわかる。

一般に、$|S|$ を2で割っていって、「1以外の、0になるまでのレベル」を作ることができる。

レベル   0   1   2   3   4   5   6   7
        18   9   4   2   1   0
作れる   o   o   o   o   x   o   x   x   ...

このように同じにならなければならない箇所は $S$ の中身によらず、$K$ と $|S|$ のみから決まるので、まずそれを求める。
（考えるのが面倒だったのでUnion-Find木を使ったが、多分ちゃんと計算すれば $O(|S|)$ で求められるはず）

そして、同じグループごとに $S$ から文字の出現回数を数えて、元からあるのが一番多い文字にそろえるのが、変更が一番小さくなる。

しかし、「ちょうど」レベル $K$ にしなければいけない。

レベルが過剰になってしまうというのは、たとえば上記の例でレベル2にしたいのに、 一番多い文字を採用すると $S_{0～3}$ が回文になってしまうようなケース。その場合レベル3以上となってしまう。

そのため、各グループ「何の文字に変更したか」「1番目でなく2番目に出現回数の多い文字を採用した場合、書き換える必要のある文字数は1番目を採用した場合から何文字増えるかの差分」を記録する。

回文となってはいけない場所が、変更の結果、回文となってしまっていないか確認し、 なっているなら差分のうち一番小さいものを2番目の文字に書き換えて回文を崩す。

そうするとちょうどレベル $K$ が保証される。

Python3

from collections import defaultdict, Counter


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self.root(x)]


k = int(input())
s = input()

r = len(s)
uft = UnionFind(len(s))
for _ in range(k):
    if r == 0:
        print('impossible')
        exit()
    for i in range(r // 2):
        uft.unite(i, r - i - 1)
    r >>= 1

if r == 1:
    print('impossible')
    exit()

rrr = defaultdict(set)
for i in range(len(s)):
    rrr[uft.root(i)].add(i)

ans = 0
ccc = {}
for t, grp in rrr.items():
    cnt = Counter(map(s.__getitem__, grp))
    a = cnt.most_common(2)
    if len(a) == 1:
        ccc[t] = [a[0][0], len(grp)]
    else:
        ccc[t] = [a[0][0], a[0][1] - a[1][1]]
    ans += len(grp) - a[0][1]

if r == 0:
    print(ans)
    exit()

ng = True
replace = 1 << 60
for i in range(r // 2):
    r1 = uft.root(i)
    r2 = uft.root(r - i - 1)
    if ccc[r1][0] != ccc[r2][0]:
        ng = False
        break
    replace = min(replace, ccc[r1][1], ccc[r2][1])

if ng:
    ans += replace

print(ans)