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

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

AtCoder ABC 066 C - pushpush (4Q, 茶色, 300 点)

AtCoder AtCoder300点 ABC-C 茶色diff NoviSteps4Q データ構造テク：全体に反映させる値を別にもつ(遅延評価) deque データ構造 操作 操作:reverse 操作:挿入 考察：パリティに着目する 考察：操作・条件・目的関数を言い換える 考察：変数変換

完全に言われた通りに実装してしまうと、 O(N^{2}) の計算量となって TLE してしまうので、工夫しよう！

問題概要

空の配列に対して、以下の操作を N 回行う。 i 回目の操作では

  • 配列の末尾に値 a_{i} を挿入する
  • 配列全体を reverse する

を行う。 N 回操作後の配列の要素を順に出力せよ。

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

配列全体を reverse するのには、 O(N) の計算量を要するので、それを N 回やるのでは全体で O(N^{2}) の計算量を要してしまう。

そこで、「reverse 操作は最後にまとめてやる」ことにしよう。実は、操作を言い換えて、次のようにしても一緒なのだ！！！

i = 0, 1, \dots, N-1 に対して

  • i が偶数のときは： a_{i} を配列の末尾に挿入する
  • i が奇数のときは： a_{i} を配列の先頭に挿入する

最後に、 N が奇数の場合には、配列全体を reverse する

もしピンと来ない方は、 N = 2, 3, 4, 5 の場合を実際に手を動かしてみると納得できると思う。

このように「配列全体に対する処理（今回は reverse）を、後でまとめて全部やることにする」というテクニックは頻出だ。

この方法ならば、 O(N) の計算量で実現できる。

コード

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

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

    deque<int> deq;
    for (int i = 0; i < N; i++) {
        cin >> a;
        if (i % 2 == 0) deq.push_back(a);
        else deq.push_front(a);
    }
    if (N % 2 == 1) reverse(deq.begin(), deq.end());

    // 出力
    for (int i = 0; i < N; i++) cout << deq[i] << " ";
    cout << endl;
}