ZONeエナジープログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ

問題

atcoder.jp

考察

重要な点は

文字列反転のコストをどう工夫するか
連続した2文字が同じ文字の場合の削除のコストをどう工夫するか

文字列反転については
文字追加の操作を行いながら、反転しているかどうかの状態を持っておき
反転している場合は文字列の先頭に文字を追加し、反転していない場合は末尾に文字を追加することで解決できる。

例えばozRnonnoeが入力の場合、
文字列反転を工夫しないで操作を行うと
zononnoe
になる。
反転を工夫して同様の操作を行うと
eonnonoz
になる。

このzononnoeとeonnonozは反転しているだけの文字列同士であることが分かる。

削除のコストについては
文字追加操作後の文字列Sから一文字ずつ新たな文字列Tに文字を追加していく。

Sの反転状態を見て、反転している場合は末尾から、そうでない場合は先頭からTへ文字を追加する。
そのSからTへ文字を追加する際に、追加しようとしている文字と現在のTの末尾の文字が同じ場合は
文字は追加せず、Tの末尾の文字もTから削除することで、同じ文字が隣り合うことがない文字列を作成することができる。