ARC 094 F - Normalization (700)
解法
n文字からなる文字列の変換の典型として,
'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する
この場合でも総和のmod3は保存されることがわかる.
この非自明な必要条件が本質.
更に実験すればわかるが,1回以上の操作によって a[i] == a[i+1] なる i ができる.
ここまで得た必要条件を列挙すると,できうる文字列は
(1) mod3 の総和が s と等しい
(2) 1回以上の操作を経由すると a[i]==a[i+1] なる i がある
となる.
後は 必要条件を列挙が実は必要十分条件になっている というAtCoderの典型パターン.
実は (1) (2) を満たす文字列は N>=4で全部作ることができるらしい(証明してない)
後はDPで数え上げる.
dp[ i ][ j ][ k ][ l ]
:= ( i 文字からなる文字列で, j=1なら(2)を満たすi'が存在し, 末尾の文字がk, 総和mod3がl )
として, 次の文字によって遷移する. O(N).
メモ
これすごい.
DPでやろうとしたら無理なのには気づいた.
例えば両端の文字を持っておいて区間dpをやろうとしても
[l,x) と [x,r) -> [l,r) と遷移した後でも, s[x],s[x+1] を変化させたら再び [l,x) の範囲で操作ができるようになる可能性がある.
なのでこの方針は諦めてできる文字列の必要条件を列挙するべきだった.
