atcoder ABC 216 D - Pair of Ballsの TLE と AC 例

atcoder

atcoder.jp

・参考
AtCoder Beginner Contest 216 - YouTube

・説明
　解き方は実際にシミュレーションするものとDAG判定するものがある(参考動画参照)。今回はシミュレーションする方で解いた。
　しかし、TLEしたので原因を調べた。結論はリストをpopするときに引数を付けて A[i].pop(0) と先頭を削除したのがダメだった。pop()に引数を付けるとO(N)になる。しかし pop()と引数を付けないとO(1)ですむ(【AtCoder】TLEした時の対処法(灰色コーダー向け)【競技プログラミング】 - Qiitaを参照)。
　実装では初めに入力の a をreverseして末尾を先頭として, pop()を使った。他にもスライス、deque()など試したがTLEした。

・実装

from collections import deque
n,m=map(int,input().split())
A=[]

cnt=[[] for _ in range(n)]  #cnt[j]はjがボールの番号で、cnt[j]に何番目の筒か入れる。
for i in range(m):
    k=int(input())
    a=list(map(int,input().split()))

    a.reverse()   #入力をreverse().

    A.append(a)  #A[i]はiが筒の番号, A[i]の中身は筒にあるボールの番号.
    
    cnt[A[i][-1]-1].append(i)

que=deque()

for j in range(n):
    if len(cnt[j])==2:
        que.append(j)   #jはボールの番号.

while len(que)!=0:
    v=que.popleft()
   
    for i in cnt[v]:  #iが筒の番号.

        A[i].pop()    #pop()は早い。末尾を消す処理。pop(0)とか引数入れると遅くなる.

        #A[i][:]=A[i][1:]  #スライスも遅い.

        #A[i].reverse()   #reverseしてもTLE
        #A[i].pop()
        #A[i].reverse()

        #Aをdequeにしてもダメ.        

        if len(A[i])!=0:
            cnt[A[i][-1]-1].append(i)
            if len(cnt[A[i][-1]-1])==2:
                que.append(A[i][-1]-1)
    
for i in range(m):
    if len(A[i])!=0:
        print("No")
        exit()
print("Yes")