C. Palindromifier (Codeforces Round #676 Div. 2)

What is Programming!?

問題

https://codeforces.com/contest/1421/problem/C

問題概要

英小文字からなる文字列Sが与えられる。文字列に対して以下の操作を繰り返し行うことができる。

• を指定して、その左にあるのi-1文字を反転させた文字列を、Sの左に連結させる
• を指定して、その右にあるのn-i文字を反転させた文字列を、Sの右に連結させる

これらの操作を30回以内、文字列の長さを10⁶を超えないという条件で行い、回文を作れ。

考察

与えられた文字列が何であろうと、特定の動作を行うことで回文を作ることが可能です。

以下、例として"abcde"で示します。

まず、R 2を指定します。操作後の文字列は"babcde"となります。（太字は追加された文字）ここで、1番目と3番目の文字が同じになること、元は1番目だった文字がそれらに挟まれて2番目に来ることがポイントです。

次にL 2を指定します。操作後の文字列は"babcdedcba"となります。ここで、先頭のbを除くと、元最後尾だったeを中心に回文ができます。

最後にL 9（9の部分は一般的には「元の文字列長」*2-1となります）を指定します。この位置は初期状態の2文字目と同じ文字が入っています。最初の操作で2文字目を左に展開していた効果で、この操作により両端をその文字で揃えることができ、回文が完成します。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    cout << 3 << endl;
    cout << "L 2" << endl;
    cout << "R 2" << endl;
    cout << "R " << n * 2 - 1 << endl;
}

余談

いやこれただのパズルやん・・・。

ちなみに自分が実際に通した回答はR 2, L n - 1, R n - 1, R n * 4 - 5でした。後ろの三つでやっていることは上記解説とほぼ同じですが、最初の操作が無駄でしたね・・・。