matsueushi | AtCoder CODE FESTIVAL 2017 qualC C

目標が達成可能かどうかは、s から ‘x’ を取り除いてできる文字列が回文であるかどうかで判定できる。以後、目標が達成可能な場合を考える。

s の ‘x’ でない文字列のうち左から i 番目の文字を $cs [i]$ とする。(i = 1,…,m とする)

$ds [i]$ を $cs [i]$ と $cs [i+1]$ の間にある ‘x’ の個数とする。 $ds [0]$ を $cs [1]$ の前にある ‘x’ の数、 $ds [m]$ を $cs [m]$ の後にある ‘x’ の数と拡張しておく。

s = “xabxa” の時は、cs = [‘a’, ‘b’, ‘a’], ds = [1,0,1,0] である。

‘x’ を挿入する操作は、ds の一つの数字を +1 することに相当する。ds が左右対称となった時文字列が回文になるから、答えは l = length (ds) として $\sum_{i=1}^{\lfloor l/2 \rfloor}|ds [i] - ds [l-i+1]|$ で求められる。