https://atcoder.jp/contests/past202104-open/tasks/past202104_e

解説

https://atcoder.jp/contests/past202104-open/submissions/22645719

高度実装問題である。
配列では任意箇所の要素を削除することは時間がかかる。
先頭123個目、末尾123個目が操作されるということと、先頭と末尾にデータを挿入するという所でdequeを使えばうまく実装できそうな感じがする。
dequeを使えば、先頭末尾に対してデータを追加したり削除したりできる。

dequeを使ってA～Cをどうやって扱うか

例えば、操作Aでは、前から1番目なので、dequeのfrontとpop_frontで単に先頭を持ってくればいい。

操作Bではどうだろうか。
これは先頭をpop_frontしてどこかに退避しておいて、もう一度frontとpop_frontすれば2番目が持ってこれる。
その後、退避しておいたデータを先頭に戻せば2番目だけが消せる。

操作Cも全く同じような操作を行う。
退避するデータはstackに入れておくのがオススメ。
123と入っていた場合、1を出して、2を出して、3を出した場合、出す順番は1→2だったが、入れる順番は2→1となる。
そうすると3だけ消したような状況を再現できる。
stackではFILO（先入れ後だし）なので、このような場面ではピッタリだ。

自分の実装では、こういった処理をpop_front関数としてモジュール化している。

他の操作

操作L,Rは普通にdequeで足すだけ。
操作D～Fについて、これはA～Cと比べて、先頭と末尾くらいの違いしかないので、頑張る。

int N; string S;
deque<int> deq;
//---------------------------------------------------------------------------------------------------
#define error "ERROR"
string pop_front(int idx) {
    if (deq.size() <= idx) return error;

    stack<int> tmp;
    rep(i, 0, idx) {
        tmp.push(deq.front());
        deq.pop_front();
    }

    int res = deq.front();
    deq.pop_front();

    rep(i, 0, idx) {
        deq.push_front(tmp.top());
        tmp.pop();
    }

    return to_string(res);
}
string pop_back(int idx) {
    if (deq.size() <= idx) return error;

    stack<int> tmp;
    rep(i, 0, idx) {
        tmp.push(deq.back());
        deq.pop_back();
    }

    int res = deq.back();
    deq.pop_back();

    rep(i, 0, idx) {
        deq.push_back(tmp.top());
        tmp.pop();
    }

    return to_string(res);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    rep(i, 0, N) {
        switch (S[i]) {
            case 'L': deq.push_front(i + 1); break;
            case 'R': deq.push_back(i + 1); break;
            case 'A': printf("%s\n", pop_front(0).c_str()); break;
            case 'B': printf("%s\n", pop_front(1).c_str()); break;
            case 'C': printf("%s\n", pop_front(2).c_str()); break;
            case 'D': printf("%s\n", pop_back(0).c_str()); break;
            case 'E': printf("%s\n", pop_back(1).c_str()); break;
            case 'F': printf("%s\n", pop_back(2).c_str()); break;
        }
    }
}

はまやんはまやんはまやん

hamayanhamayan's blog

Third from Front [第六回アルゴリズム実技検定 E]

解説

dequeを使ってA～Cをどうやって扱うか

他の操作