データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上
下
前
次
1-
新
47
(1)
: 2021/10/11(月)16:16
ID:bJ9NE0N3(1/2)
AA×
外部ﾘﾝｸ:atcoder.jp
外部ﾘﾝｸ:ideone.com
[
240
|
320
|480|
600
|
原寸
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
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
閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります の出題ページは以下になります アルゴリズム実技検定という本の解説を読みますとトポロジカルソートという考え方を使うと書いてあります 私はトポロジカルソートについて何も知りませんが制限時間内に答えを出すプログラムを書けました 本当にトポロジカルソートというのが必要でしょうか？ なお上記ページにリンクが貼ってある解説のページというユーザーの解説のページにもトポロジカルソートを知っていれば一瞬だが知らないと解けない と書いています アルゴリズム実技検定という本の模範解答を見てもトポロジカルソートによって頂点に番号を割り振ったりはしていません つまりトポロジカルソートなど不要ではないかと思うんです 以下がジャッジにパスした私ののコードです
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 58 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
ぬこの手
ぬこTOP
0.042s
