データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
47: デフォルトの名無しさん [] 2021/10/11(月) 16:16:04.73 ID:bJ9NE0N3 閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。 AtCoderの出題ページは以下になります。 https://atcoder.jp/contests/dp/tasks/dp_g 『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。 私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。 本当に「トポロジカルソート」というのが必要でしょうか？ なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」 と書いています。 『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。 つまり「トポロジカルソート」など不要ではないかと思うんです。 以下がジャッジにパスした私のPythonのコードです。 https://ideone.com/iQIvcc http://mevius.5ch.net/test/read.cgi/tech/1580131715/47
48: デフォルトの名無しさん [] 2021/10/11(月) 16:25:53.01 ID:bJ9NE0N3 >>47 あともう一点。 この問題の出題カテゴリは動的計画法に属します。 『アルゴリズム実技検定』の模範解答も私のコードも、深さ優先探索 + 「メモ化再帰」で答えを計算しています。 >>45 確かにこの問題の場合部分問題重複性はあると思いますが、こういう単なる、いわゆる「メモ化再帰」も動的計画法と言っていいのでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/48
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.526s*