[Codeforces] Codeforces Round #676 C. Palindromifier

問題

方針

どちらの操作も \( S \) の先頭または末尾の文字を含む部分列を選ぶことができないので、\( S \) の末尾が中心となるような回文を作ることを考えます。

まず初めに、”L 2″ という操作を行うと、

\[ s = s_{2}s_1s_2 \cdots s_{n-1}s_{n}\]

となり、長さ \( n + 1 \) の文字列が得られます。次に、\( s_1 \) を含んだ部分文字列は、\( s_1 \) または \( s_1s_2 \cdots s_{n-1} \) があります。ここで、”R 2″ という操作を行うと、

\[s = s_2s_1s_2 \cdots s_{n-1}s_ns_{n – 1}s_{n-2} \cdots s_2s_1\]

となり、長さ \( 2n\) の文字列が得られます。この文字列の末尾に、\( s_2 \) という文字を追加すると回文となるので、”R 2n-1″ という操作を行います。

コード