【AtCoder】ABC 411 D - Conflict 2 | 緑コーダーが解くAtCoder

atcoder.jp

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1018 / NoviSteps: 1Q

問題概要
制約
考察
- 永続配列を利用する
- クエリを逆読みする
実装例
- 考察1
- 考察2
コメント

問題概要

$1$ 台のサーバーと $N$ 台のPCがある。サーバーおよび各PCはそれぞれ1つずつ文字列を保持しており、最初は全て空文字列である。

$Q$ 個のクエリが与えられるので、全てのクエリを与えられた順に処理したときの最終的なサーバーの文字列を求めよ。各クエリは以下のいずれかの形式である。

1 p：PC $p$ の文字列をサーバーの文字列で置き換える。
2 p s：PC $p$ の文字列の末尾に文字列 $s$ を追加する。
3 p：サーバーの文字列をPC $p$ の文字列で置き換える。

制約

$N,Q$ は整数
$1\leq N,Q \leq 2\times 10^5$
全てのクエリについて、 $p$ は整数であり $1 \leq p\leq N$ を満たす
全ての2種類目のクエリについて、 $s$ は英小文字からなる長さ $1$ 以上の文字列
全ての2種類目のクエリに対する $s$ の長さの総和は $10^6$ 以下

考察

3つのクエリ操作で配列全体に関わるようなものはないので、愚直にシミュレーションしても通りそうだが...

https://atcoder.jp/contests/abc411/submissions/66950771

さすがはD問題。そんなにうまい話はない。

実は、クエリ1や3において文字列のコピーが発生しているのが原因である。

qiita.com

これを回避するために、2つの解法を紹介する。

永続配列を利用する

通常のデータ構造で、更新をするときに更新前の状態のデータも保存しておけるデータ構造を「永続データ構造」という。今回は、その配列版を用いることにする。

具体的には、以下のような「状態」を要素に持つ配列を作成する。

この状態の更新元になった状態の $\mathrm{id}$ と、新たに追加される文字列 $s$ とのペア : $(\mathrm{id}, s)$

図にするとこんな感じ。木構造をイメージした方が分かりやすいかもしれない。

サーバーや各PCは、この配列(木構造)の index (頂点番号) を参照するようにする。つまり、各クエリでは以下のような処理を行う。

クエリ1 : $\mathrm{pc}_{p} = \mathrm{server}$ とする。
クエリ2 : 新たな状態 $(\mathrm{pc}_{p}, s)$ を作成する。その後、 $\mathrm{pc}_{p}$ の参照をその状態の index とする。
クエリ3 : $\mathrm{server} = \mathrm{pc}_{p}$ とする。

これで、各クエリの処理は $O(1)$ の計算量で済ますことができた。

次に、最終的なサーバーの文字列を復元していく。

これは、全クエリ処理後の $\mathrm{server}$ が参照している状態の index から始めて、各状態の $\mathrm{id}$ を辿っていけばよい(木構造で、葉から親に向かってさかのぼるイメージ)。

実装においては、文字列のコピーが発生しないように注意すること(1敗)。実装例の59行目から71行目を参考にするとよい。

クエリを逆読みする

この問題ではサーバーと各PCは同一視できるので、便宜上サーバーをPC $0$ とする。

その上で、 $q$ 番目のクエリ処理後のPC $i \: (0 \leq i \leq N)$ の文字列の状態を $(q, i)$ とする。これらの状態は、各クエリで以下のように変化する。

クエリ1 : $(q, p) = (q-1, 0), \quad i \neq p を満たす全ての i に対して (q, i) = (q-1, i)$
クエリ2 : $(q, p) = (q-1, p) + s, \quad i \neq p を満たす全ての i に対して (q, i) = (q-1, i)$
クエリ3 : $(q, 0) = (q-1, p), \quad i \neq 0 を満たす全ての i に対して (q, i) = (q-1, i)$

最終的に求めたいのは $(Q, 0)$ であるが、これは $Q$ 個のクエリを逆から見ていくことで、結果的に $(0, i)$ まで到達できる。

この初期状態に到達するまでに、経由したクエリ2にて追加される文字列 $s$ を逆順にして末尾に結合していき、最後に全体を反転させれば答えを得ることができる(実装例を参考のこと)。

実装例

考察1

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

struct Node
{
    int prev;
    string str;
};

int main()
{
    int N, Q;
    cin >> N >> Q;

    int server = 0;
    vector<int> pc(N);
    vector<Node> list;

    list.push_back({-1, ""});

    while (Q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int p;
            cin >> p;
            p--;

            pc[p] = server;
        }
        else if (t == 2)
        {
            int p;
            string s;
            cin >> p >> s;
            p--;

            int cur = pc[p];
            pc[p] = list.size();
            list.push_back({cur, s});
        }
        else if (t == 3)
        {
            int p;
            cin >> p;
            p--;

            server = pc[p];
        }
    }

    vector<string> ans;
    int current_id = server;
    while (current_id != -1)
    {
        if (!list[current_id].str.empty())
        {
            ans.push_back(list[current_id].str);
        }

        current_id = list[current_id].prev;
    }

    reverse(all(ans));

    for (auto &&s : ans)
    {
        cout << s;
    }
    cout << endl;

    return 0;
}

atcoder.jp

考察2

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

// ======================================== //

struct Query
{
    int type;
    int p;
    string str;
};

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<Query> queries(Q);
    rep(i, 0, Q)
    {
        int t, p;
        cin >> t >> p;
        if (t == 2)
        {
            string s;
            cin >> s;
            queries[i] = {t, p, s};
        }
        else
        {
            queries[i] = {t, p, ""};
        }
    }

    string ans = "";
    int current_id = 0;
    rrep(q, Q - 1, 0)
    {
        if (queries[q].type == 1)
        {
            if (current_id == queries[q].p)
            {
                current_id = 0;
            }
        }
        else if (queries[q].type == 2)
        {
            if (current_id == queries[q].p)
            {
                reverse(all(queries[q].str));
                ans += queries[q].str;
            }
        }
        else if (queries[q].type == 3)
        {
            if (current_id == 0)
            {
                current_id = queries[q].p;
            }
        }
    }

    reverse(all(ans));

    cout << ans << endl;

    return 0;
}