競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新

---

200(1): (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/10(月)22:32 ID:GqegRxcS0(4/4) AA×

外部ﾘﾝｸ:ideone.com

[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
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
この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はです 頂点間に循環がないため再帰の深さが頂点数を超えることがなく 各頂点に対して 関数が最大回しか呼び出されないからです トポロジカルソートを使ってそのコードを書き換えるとこうなります

---

上下前次1-新書関写板覧索設栞歴

---

あと 278 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.017s