Atcoder ABC294-DのTLEの解消方法を教えてください

Question

ABC294-DのTLEの解消

AtcoderのABC294のD問題 (https://atcoder.jp/contests/abc294/tasks/abc294_d) に以下のコードを提出したのですが、どうしてもTLEになります
問題の説明は実際の問題を見たほうがわかりやすいので省きます

プログラムの説明
l1で呼ばれたけど行っていない人、l0で呼ばれてない人を管理しています
入力の1文字目が1の時はl0の最小値をheappopしてl1に加えます
1文字目が3の時はl1の最小値を出力します
1文字目が2の時はそれに続く数字をl1からremoveします

import heapq
n,q=map(int,input().split())
l1=set([])
l0=list(range(1,n+1))
for j in range(q):
    a=input().split()
    if a[0]=="1":
        x=heapq.heappop(l0)
        l1.add(x)
    elif a[0]=="3":
        print(min(l1))
    else:
        l1.remove(int(a[1]))

頑張ってTLEを減らしたんですが、どうしても 01_random_06.txt と 01_random_09.txt という二つのケースのみでTLEが出ます
A, B, CとACしてそのあと80分くらいずっとこのTLE解消しようとしていて(絶対E問題を見るべきだった)コンテスト終了したので、結構悔しいです
なぜTLEになるのか、どうしたら解決できるのか、教えていただきたいです
よろしくお願いします

捕捉
以下のコードでも同じケースのTLEで引っかかりました

n,q=map(int,input().split())
l=[0]*n
p=[]
l0m=1
l1=set([])
for j in range(q):
    a=input().split()
    if a[0]=="1":
        l1.add(l0m)
        while l0m in l1:
            l0m+=1
    elif a[0]=="3":
        print(min(l1))
    else:
        l1.remove(int(b))

できればこのTLEの解説もお願いしたいです

Comments

[Zuishin]

set が hashtable なので、min に時間がかかっています。

[FGcoder]

コメントありがとうございます
listに変えてみましたが、なぜかわかりませんがむしろTLEが11に増えてしまいます

[Zuishin]

list だと remove に時間がかかります。

[actorbug]

このあたりが参考になりませんかね。

【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】
https://qiita.com/nebocco/items/638da118cd621d2628d1

[melian]

for j in range(q):
を
for j in range(q//10):
に変更して実行してみてください。すべて WA になりますが、01_random_06.txt と 01_random_09.txt の実行時間が 200 ms を超えていることが判るかと思います。

[Zuishin]

というより、せっかくヒープを使っているのになぜわざわざ他の構造に移すのかわかりません。
受付に足を運ぶ時も、再度呼ばれる時も、既に一度呼ばれていることが保証されているのだから、l0 を丸々 l1 として使用して最初から全員呼ばれたものとして扱い、1 の入力を無視すればいいのでは？

[FGcoder]

返答遅れてすみません
list だと remove に時間がかかります。
>>なるほどです
このあたりが参考になりませんかね。...
>>資料をありがとうございます、勉強させていただきます
for j in range(q): ...
>>やってみましたがその通りでした
というより、...
>>これは目からうろこでした
不必要な情報を処理していたんですね

Answer 1

私は普段pythonを使っているわけではないので，完全な答えではないかもしれません。その点ご了承ください。
計算量を悪化させているのはprint(min(l1))の部分だと思われます。setは順序を記憶しないため，最小値を返そうとするとどうしてもすべての要素を見る必要があるからです。
以下のコードはAtCoder上のコードテストにて10秒以上要します。(終了コード9，すなわちTLEが出ます。)

l1=set([])

for i in range(100000):
  l1.add(i)

for _ in range(100000):
  print(min(l1))

一方，以下のコードはTLEになりません。(70ms程度でした)

l1=list([])

for i in range(100000):
  l1.append(i)

for _ in range(100000):
  print(l1[0])

(添え字によるO(1)アクセスは違うだろと思うかもしれませんが，単にmin()がネックになっていると言いたいだけです。)
解決策としては，actorbugさんの回答を参考にするとよいと思います。

Comments

[FGcoder]

ありがとうごぜいます
minの扱いには注意します

Answer 2

TLE の理由については、コメントで Zuishin さんがおっしゃっている通りで、set の min が遅いからです。
より詳しくは、「特集！知らないと損をする計算量の話」を参照してください。同ページの「3-4. 様々な言語での事情」に、様々なデータ構造における計算量がまとめられています。

解決方法については、コメントで伝えた「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】」を参照してください。試しに、同ページの「解決法3: 優先度付きキュー」からコードを(変数名だけ変えて)コピペして、l1の代わりにそちらを使ったところ、ACになりました。

import heapq
hp = list()
hq = list()

def insert(x):
    heapq.heappush(hp, x)
    return

def erase(x):
    heapq.heappush(hq, x)
    return

def minimum():
    while hq and hp[0] == hq[0]:
        heapq.heappop(hp)
        heapq.heappop(hq)
    return hp[0]

n,q=map(int,input().split())
l0=list(range(1,n+1))
for j in range(q):
    a=input().split()
    if a[0]=="1":
        x=heapq.heappop(l0)
        insert(x)
    elif a[0]=="3":
        print(minimum())
    else:
        erase(int(a[1]))

それ以外にも、公式の解説で説明されている「解法 2 (線形時間で解く方法)」をPythonで実装する方法もあります。

追記

AtCoderだと、sortedcontainers というライブラリが使えるそうです。(atcoder新ジャッジのpypy3.10で入っているライブラリたちを確認より)
こちらでもACできることを確認しました。

from sortedcontainers import SortedList
import heapq
n,q=map(int,input().split())
l1=SortedList()
l0=list(range(1,n+1))
for j in range(q):
    a=input().split()
    if a[0]=="1":
        x=heapq.heappop(l0)
        l1.add(x)
    elif a[0]=="3":
        print(l1[0])
    else:
        l1.remove(int(a[1]))

Comments

[FGcoder]

具体的な解決のコードまで乗せてくださりありがとうございます