AtCoder CODE FESTIVAL 2017 qualC C - Inserting 'x'

目標が達成可能かどうかは、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]|$ で求められる。