問題
有向非巡回グラフであり、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):