AtCoderの問題で、DAGの最長経路に帰着させる問題を解いたのですが、どうしてもTLEしてしまいます。
問題はこちら。
言語はPyPy3を使用しています。
各試合(i,j)自体を頂点とし、頂点数|V|=N(N-1)/2、辺の数|E|=N(N-1)として、試合の順番を辺とした有向グラフと見做すようです。
O(N^2)で計算できていると自分では思っているのですが、Topological sort,最長経路計算の処理に無駄があるのでしょうか?
それとも別の場所の処理が時間を食っているのでしょうか?
まだまだ若輩者ですので、ご教授いただけると幸いです。
提出したコードを以下に記載しておきます。
Python
1import sys 2input=sys.stdin.readline 3def resolve(): 4 #%% import 5 from itertools import product 6 from collections import deque 7 8 #%% input 9 n=int(input()) 10 V=[(i,j) for i,j in product(range(n),range(n)) if i<j] 11 N=len(V) # N=n*(n-1)//2 12 13 #%% adjacency list 14 outs={v:[] for v in V} 15 indeg={v:0 for v in V} 16 for i in range(n): 17 edge=list(map(lambda x:int(x)-1,input().split())) 18 for j in range(len(edge)-1): # 各iにつきn-1個の辺が与えられる 19 v0 = (min(i,edge[j]),max(i,edge[j])) 20 v1 = (min(i,edge[j+1]),max(i,edge[j+1])) 21 outs[v0].append(v1) 22 indeg[v1]+=1 23 24 #%% topological sort 25 Q=deque(v for v in V if indeg[v]==0) 26 res=[] 27 while(Q): 28 v0=Q.popleft() 29 res.append(v0) 30 for v1 in outs[v0]: 31 indeg[v1]-=1 32 if indeg[v1]==0: Q.append(v1) 33 34 #%% judge whether G is DAG 35 if len(res)<N: 36 print("-1") 37 return 38 39 #%% Longest Path Problem 40 LP={v:1 for v in V} 41 for v0 in res: 42 for v1 in outs[v0]: 43 LP[v1]=max(LP[v1],LP[v0]+1) 44 print(max(LP.values())) 45 46resolve()
あなたの回答
tips
プレビュー