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

エンジニアリングのことはもちろん、全然関係無い話もします。

【AtCoder Beginner Contest 134】感想戦

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

ABC134

過去のABC参加履歴

最近、過去問もあまり解けてなくて不安だったのですが。
単に相性が良かったのと、D問題までペナルティを喰らわなかったことが大きかったと思います。

方針の計算量を意識することができるようになってきたことも良かったと思っています。

ただ、なんといっても今回残念だったのはE問題・・・

残り約20分の時点で O(n\log n)の方針が立ち、これは行ける・・・!と思ったのですが、なぜか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。

ネットリテラシーも実力のうち。
とはいえ、めっちゃ悔しい。

やはり、なにか新しいパッケージを試すときは、まずは絶対に公式リファレンスは確認しようと思ったのでした。