データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
47(1): 2021/10/11(月)16:16:04.73 ID:bJ9NE0N3(1/2)調 AAS
閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。
AtCoderの出題ページは以下になります。
https://atcoder.jp/contests/dp/tasks/dp_g
『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。
私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。
本当に「トポロジカルソート」というのが必要でしょうか？
なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」
と書いています。
『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。
つまり「トポロジカルソート」など不要ではないかと思うんです。
以下がジャッジにパスした私のPythonのコードです。
https://ideone.com/iQIvcc
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.017s