[Codeforces] Codeforces Round #676 C. Palindromifier

2020年10月19日2020年12月12日

問題

方針

どちらの操作も \( 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″ という操作を行います。

コード

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

int main() {
    string S;
    cin >> S;
    int n = S.length();
    cout << "3\n";
    cout << "L " << 2 << "\n";
    cout << "R " << 2 << "\n";
    cout << "R " << 2 * n - 1<< "\n";
    return 0;
}