[AtCoder] ABC 158 D – String Formation

2020年3月8日2020年12月15日

問題

方針

文字列 \( 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 }^*\) となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string S;
    int Q;
    cin >> S >> Q;
    deque<char> l, r;
    bool flag = true;
    int T, F;
    char C;
    for (int i = 0; i < Q; i++) {
        cin >> T;
        if (T == 1) flag = !flag;
        else {
            cin >> F >> C;
            if (F == 1) {
                if (flag) l.push_front(C);
                else r.push_back(C);
            } else {
                if (flag) r.push_back(C);
                else l.push_front(C);
            }
        }
    }
    if (flag) {
        for (char c : l) cout << c;
        cout << S;
        for (char c : r) cout << c;
        cout << "\n";
    } else {
        while (!r.empty()) {
            cout << r.back();
            r.pop_back();
        }
        reverse(S.begin(), S.end());
        cout << S;
        while (!l.empty()) {
            cout << l.back();
            l.pop_back();
        }
        cout << "\n";
    }
    return 0;
}