問題
有向非巡回グラフであり、DP の更新順序が非自明な問題です。
メモ化再帰を使うか、トポロジカルソートを使います。
解き方は以下を参考にしています。
Educational DP Contest の F ~ J 問題の解説と類題集 G 問題 – Longest Path
回答
メモ化再帰
import sys # 許容する再帰処理の回数を変更 sys.setrecursionlimit(10**5+10) # input処理を高速化する input = sys.stdin.readline def chmax(a, b): """ 最大値を返す関数 """ if a >= b: return a else: return b def main(): # 入力 N, M = map(int, input().split()) # 隣接関係は隣接リストで管理する lst_edge = [[] for _ in range(N)] for _ in range(M): x, y = map(int, input().split()) # 最初のindexをゼロにする lst_edge[x-1].append(y-1) # dp[v] := ノードvを始点とした時の有向パスの長さの最大値 # -1 未訪問で初期化。 dp = [-1] * N # メモ化再帰 def rec(v): # 既に更新済み if dp[v] != -1: return dp[v] ans = 0 lst_nv = lst_edge[v] for nv in lst_nv: ans = chmax(ans, rec(nv) + 1) dp[v] = ans return dp[v] # 全ての点に対して更新する ans = 0 for v in range(N): ans = chmax(ans, rec(v)) print(ans) main()
トポロジカルソート
dequeオブジェクトを使います。
import sys import collections # input処理を高速化する input = sys.stdin.readline def chmax(a, b): """ 最大値を返す関数 """ if a >= b: return a return b def main(): # 入力 N, M = map(int, input().split()) # 隣接関係は隣接リストで管理する lst_edge = [[] for _ in range(N)] # 各頂点の入力辺の本数 deg = [0] * N for _ in range(M): x, y = map(int, input().split()) # 最初のindexをゼロにする lst_edge[x-1].append(y-1) deg[y-1] += 1 # 入力辺を持たない頂点をqueueに入れる que = collections.deque() for v in range(N): if deg[v] == 0: que.append(v) # 各頂点の最初に入力辺を持たなかった点からの距離 dp = [0] * N # For sequences, (strings, lists, tuples), use the fact that empty sequences are false. # https://www.python.org/dev/peps/pep-0008/#programming-recommendations while que: v = que.popleft() lst_nv = lst_edge[v] for nv in lst_nv: # エッジ(v, nv)をグラフから削除する deg[nv] -= 1 if deg[nv] == 0: # エッジがなくなったことで、入力辺がなくなったらqueueに入れる que.append(nv) # 最初に入力辺を持たなかった点からの距離 dp[nv] = chmax(dp[nv], dp[v] + 1) print(max(dp)) main()
sequenceが空かどうかの判定
「空のsequenceはFlaseである」ということを使うこと。PEP 8推奨だし、多分一番速い。
Yes: if not seq: if seq: No: if len(seq): if not len(seq):