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

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

AtCoder ABC 158 D - String Formation (400 点)

先頭と末尾の両方から 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 つ

  1. 文字列 S を反転する
  2. 文字列 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;
}