ABC-066 C pushpush を解いてみた

ABC-C 066を解いたのですが、今回の問題はデータ構造を知っているか知らないかの問題で解けたのですが、最初、提出した際に TLE でできなかったのでなんでかなとおもったら使っていた STL のメソッドが悪かったようでした。 今回はデータ構造について学ぶことが多く良問でした。

では、以下問題

問題 C - pushpush

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

長さ n の数列 ai ,..., an が与えられます。 空の数列 b に対して、以下の操作を n 回行うことを考えます。 i 回目には数列の i 番目の要素 ai を b の末尾に追加する。b を逆向きに並び替える。この操作をしてできる数列 b を求めて下さい。

制約

  • 1 ≤ n ≤ 2 × 105
  • 0 ≤ ai ≤ 109
  • n,ai は整数である。

とこんな感じ 見た感じ結構複雑な操作をしていますが、実はそうでもないものです。おそらく面食らうのは逆向きにならべかえるという部分ですが、実際にはこの作業は不要になります。並び変えをすると特定条件で最速でもO(N) 最悪の場合 O(N2) で制約からすると最大のNは 105 なのでこの操作は避けたいっといったところです。

考えたこと

並び替えが発生するのを避けたいので、並び替えをしなくてもいい方法を見つけました。ここで注目するのは最初の入力のNとループを回す変数になります。 ループを回している変数が偶数の場合は反転×反転なので追加する場所は変わらないので、最初に要素が挿入されます。逆に奇数の場合は1回の反転なので最後に要素が挿入されます。 こうすると途中の並び替えの操作が不要になります。 Nが偶数の場合はもとの状態なので反転させる必要があるため、末尾要素から出力していき、Nが奇数の場合はすでに反転しているので最初から出力していくというものになります。

フロー

  • 入力受け取り
  • キューを定義
  • Nに対して線形ループを行う
    • もしループの変数が偶数ならば以下の処理
      • キューの最初に追加をする
    • それ以外ならば
      • キューの最後に定義
  • もしNが偶数ならば
    • キューの末尾からループを行う
      • キューの出力
  • それ以外ならば
    • キューの最初からループを行う
      • キューの出力

みたいな感じです。 ここでなぜキューを使っているかというとVector配列だと 最初の要素に入れる関数がinsertになってしまい。これはメモリを線形探索して最初の要素を探すということをしているらしいのでinsertを使うと実質 N2 のオーダになってしまうということになります。

プログラム

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;

int main(void){
    int N;
    cin >> N;
    vector<long long> a(N);
    deque<long long> b;

    for(int i = 0;i < N;i++){
        cin >> a[i];
    }

    for(int i = 0;i < N;i++){
        if(i % 2 == 0){
            b.push_front(a[i]);
        }else{
            b.push_back(a[i]);
        }
    }
    if (N % 2 == 0){
        for(int i = b.size() - 1;i >= 0;i--){
            cout << b[i] << " ";
        }
    }else {
        for(int i = 0; i < b.size(); i++){
            cout << b[i] << " ";
        }
    }

    return 0;
}

これでACとれました