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]| \) で求められる。