【精進記録】AtCoder Beginner Contest 066 C - pushpush

問題

beta.atcoder.jp

解法

TLEしか出せなかったので解説を見てAC．

最初に追加した要素ほど数列の中央側になっていくので，要素のindexの偶奇に気をつけて数列の前と後ろに交互に要素を追加していけば良い．

解法自体は思いついたが単純にPythonのリストに対してappend()で後ろに追加，insert()で先頭に追加，という方法をしていたのがよくなかった．
特にinsertは計算量がO(n)なので遅いらしい．
参考：

qiita.com

解説を見たところ，C++の場合はdequeというライブラリを使うと簡単にできると記されていたので，Pythonにも存在するか調べたところ，collectionモジュールにdequeが含まれていたのでこれを利用しました．

insert()の代わりにdequeのappendleft()を使えば計算量がO(1)になるようです．

コード

from collections import deque
 
N = int(input())
A = [int(i) for i in input().split()]
 
B = deque(maxlen=2*10**5)
 
if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])
 
print(*B)