[Python] Educational DP Contest G – Longest Path

問題

G – Longest Path

有向非巡回グラフであり、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オブジェクトを使います。

Python 標準ライブラリ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):

PEP 8 — Style Guide for Python Code