Web系エンジニアのアウトプット練習場

エンジニアリングと書評が中心。たまに全然関係無い話もします。
トップページ/競技プログラミング/【AtCoder Beginner Contest 134】感想戦/
2019年07月21日

【AtCoder Beginner Contest 134】感想戦

競技プログラミングAtCoder

今回はA,B,C,Dの4完!
過去の最高のパフォーマンスを大幅更新することができました。




最近、過去問もあまり解けてなくて不安だったのですが。
単に相性が良かったのと、D問題までペナルティを喰らわなかったことが大きかったと思います。
方針の計算量を意識することができるようになってきたことも良かったと思っています。
ただ、なんといっても今回残念だったのはE問題・・・
残り約20分の時点でO(nlogn)の方針が立ち、これは行ける・・・!と思ったのですが、なぜかTLE。
そのときのコードがこんな感じ。

import bisect
 
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
 
ans = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(ans, A[i])
    if index > 0:
        ans[index - 1] = A[i]
    else:
        ans.insert(0, A[i])
 
print(len(ans))

よくよく調べてみるとO(1)だと思っていたans.insert(0, A[i])の計算量がO(n)だということがわかりました。
これを回避するためにdequeというパッケージを見つけ、insertの部分を変えたのですがまさかのRE。
初めて使ったライブラリだったため、なぜREするのかがわからず、10分を無駄にし、あえなく終了。
あとで冷静にライブラリの公式リファレンスを見ると、typo(appendleftappendLeftになってた)が判明。
どうやら、参考にしたブログがそもそもtypoしてたようで。
コンテスト終了直後に、typoを直して提出してみると無事AC。
ネットリテラシーも実力のうち。
とはいえ、めっちゃ悔しい。
やはり、なにか新しいパッケージを試すときは、まずは絶対に公式リファレンスは確認しようと思ったのでした。