先頭と末尾の両方から push できるデータ構造といえば、deque！！！

問題概要

長さ $N$ の文字列 $S$ が与えられる。以下の $Q$ 個の操作を行ってできる文字列を出力せよ

type 1：文字列 $S$ を左右反転する
type 2：値 F と文字 c が与えられ、F = 1 のときは $S$ の先頭に文字 c を付け加え、F = 2 のときは $S$ の末尾に文字 c を付け加える

制約

$1 \le N \le 10^{5}$
$1 \le Q \le 2 \times 10^{5}$

考えたこと

愚直にやったのでは間に合わない。毎回のクエリを $O(1)$ くらいで処理する必要がある。難所は 2 つ

文字列 S を反転する
文字列 S の「先頭」に文字 c を付け加える

これらのいずれも単純にやると $O(N)$ の計算時間がかかってしまうのだ。

1. 文字列 S の反転について

文字列を反転させる代わりに、「今は反転状態」「今はデフォルトの向きの状態」という状態を管理するフラグ rev を持たせることにする。これにともない、type 2 のやり方をちょっとだけ修正する。

rev = True のとき

F = 1 のときは、S の末尾に c を追加
F = 2 のときは、S の先頭に c を追加

rev = False のとき

F = 1 のときは、S の先頭に c を追加
F = 2 のときは、S の末尾に c を追加

という風に処理を分岐すれば OK！！！

2. 文字列 S の「先頭」に文字 c を付け加える

普通に

S = c + S

という風にしたのでは $O(N)$ の計算量がかかってしまう。そこで、文字列を

deque 型

で扱うとちょうどよい。deque は

push_front：先頭に追加
pop_front：先頭を削除 (今回は不要)
push_back：末尾に追加
pop_back：末尾に削除 (今回は不要)

をすべて、ならし $O(1)$ でできるのだ。全部で $O(N+Q)$ でできる。なお、他にもめちゃくちゃ沢山の方法がある (下に)。

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

int main() {
    string S;
    cin >> S;
    deque<char> dS(S.size());
    for (int i = 0; i < S.size(); ++i) dS[i] = S[i];

    int Q; cin >> Q;
    int rev = 0;
    for (int i = 0; i < Q; ++i) {
        int type; cin >> type;
        if (type == 2) {
            int f; char c;
            cin >> f >> c; --f;
            if (rev) f = 1 - f; // 反転状態だったら、フラグを反転
            if (f == 0) dS.push_front(c);
            else dS.push_back(c);
        }
        else rev = 1 - rev;
    }
    if (rev) reverse(dS.begin(), dS.end());
    for (auto c : dS) cout << c;
    cout << endl;
}

別解：その他の方法

他にもたくさんの方法がある

反転はフラグ管理する方法

deque (今回の)
linked list
stack (普通の vector でも string でも OK) を 2 つ使う
queue を 2 つ使う
string でも insert(0, c) によって先頭に追加すれば、メチャ高速で通るらしい

反転を真っ向から扱う方法

Treap などの平衡二分探索木を使う

ここでは「string を 2 つ使う」という方法でやってみよう。

解法 (2)： string を 2 つ使う

以下の 2 つを持つことにする

先頭に付け加えることになる文字列 $X$
末尾に付け加えることになる文字列 $Y$

ただし $X$ については反転した状態で管理することにする。また初期状態ではこれらは空文字列で初期化しておく。そうすると

S の先頭に c を追加する処理： X += c
S の末尾に c を追加する処理： Y += c

という風に簡潔に書ける。そして最後に、

X を反転
X + S + Y を出力 (rev = True なら全体を反転)

とすれば OK。

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

int main() {
    string S, X, Y;
    cin >> S;

    int Q; cin >> Q;
    int rev = 0;
    for (int i = 0; i < Q; ++i) {
        int type; cin >> type;
        if (type == 2) {
            int f; char c;
            cin >> f >> c; --f;
            if (rev) f = 1 - f; // 反転状態だったら、フラグを反転
            if (f == 0) X += c;
            else Y += c;
        }
        else rev = 1 - rev;
    }
    reverse(X.begin(), X.end());
    string res = X + S + Y;
    if (rev) reverse(res.begin(), res.end());
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 158 D - String Formation (茶色, 400 点)

問題概要

制約

考えたこと