競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
190: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:12:48.08 ID:GqegRxcS0 確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、 実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、 トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。 その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、 その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。 この順序付けがトポロジカルソートの結果と同じです。 indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、 indegreeが0になる頂点が次々と現れます。この手順は、トポロジカルソートを実行する手順と同じです。 したがって、トポロジカルソートを明示的に行わなくても、その考え方が解法に含まれているため、 問題を解決することができます。トポロジカルソートの概念は、DAGの最長パス問題を解く際の重要な考え方であることがわかります。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/190
192: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:19:57.68 ID:GqegRxcS0 はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。 繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、 この順序付けに従ってDPを適用することで、最長パスを求めることができます。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/192
194: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 16:26:05.43 ID:GqegRxcS0 トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。 ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。 トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。 ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、 各頂点と辺に対して一度だけ計算が行われます。 一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。 例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。 これは、全ての頂点に対して、それぞれを含むか含まないかの選択肢があるためです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/194
200: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/10(月) 22:32:19.30 ID:GqegRxcS0 この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。 頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、 各頂点に対して rec 関数が最大1回しか呼び出されないからです。 トポロジカルソートを使ってそのコードを書き換えるとこうなります。 https://ideone.com/1NbHIf http://mevius.5ch.net/test/read.cgi/tech/1679465982/200
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.018s