[AtCoder] ABC 158 D – String Formation

問題

方針

文字列 \( S \) を前後を反転してできる文字列を \( S^* \) とします。\( S \) の先頭に追加された文字列を \( L \) とし、末尾に追加された文字列を \( R \) とすると、最終的な文字列は、\( LSR \) または \(R^*S^*L^* \) となります。ここで、\( T_i = 1 \) となった回数を \( k \) とし、\( i \) 番目の操作で得られる文字列を \( L_i, R_i \) とします。

\( k \bmod 2 = 0 \wedge T_i = 2\) のとき

現状の文字列は \( L_{i -1}SR_{i – 1}\) となっているので、\( F_i \) の値によって \(L_{i-1} \) の先頭または、\( R_{i-1} \) の末尾に文字を追加します。この操作が終わった時の文字列は、\( L_{i}SR_{i}\) となります。

\( k \bmod 2 = 1 \wedge T_i = 2\) のとき

現状の文字列は \( R_{i -1}^*S^*L_{i – 1}^*\) となっています。\( F_i = 1 \) のとき、\( R_{i-1} \) の末尾に文字を追加し、\( F_i = 2 \) のとき、\( S_{i-1} \) の先頭に文字を追加します。この操作が終わった時の文字列は、\( R_{i }^*S^*L_{i }^*\) となります。

コード