データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4

**デフォルトの名無しさん** · 2020/01/27(月) 22:28:35.79

【前スレ】
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3
https://mevius.5ch.net/test/read.cgi/tech/1466315249/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

**デフォルトの名無しさん** · 2020/07/27(月) 12:25:50.05

深さ優先探索の計算時間がO(|V| + |E|)と評価されるのはなぜですか？
|V| << |E|だから、O(|E|)でOKな気がします。

**デフォルトの名無しさん** · 2020/07/27(月) 12:40:31.34

わからんけどグラフの連結性を仮定してないのでは

**デフォルトの名無しさん** · 2020/07/27(月) 15:17:43.62

>>2
|E| < |V|^2 だぞ

**デフォルトの名無しさん** · 2020/09/22(火) 22:37:15.01

２つの同数の点集合A,Bがあって
１対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか

具体的にはa_i∈A, b_j∈B
i->j : j(i)
Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i)

**デフォルトの名無しさん** · 2020/09/22(火) 23:17:08.08

二部グラフの最小重み完全マッチングでいけないかな

**デフォルトの名無しさん** · 2020/09/22(火) 23:22:00.48

でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな
それならハンガリアン法とか最小費用流で解けるのでは

**デフォルトの名無しさん** · 2020/09/22(火) 23:31:12.82

ありがとうございます
調べてみます

**デフォルトの名無しさん** · 2020/11/08(日) 15:47:31.10

開票所要時間は理論上 O(log n) だよね？

【米大統領選】日本なら一晩で終わる開票作業　なぜそんなに時間がかかったのか(デイリー新潮)
https://news.yahoo.co.jp/articles/e7f705c442fa18c1455c579a7cd209861ef6212b

**デフォルトの名無しさん** · 2020/11/08(日) 15:50:45.10

アルゴリズムで書いたら判定してやるよ

**デフォルトの名無しさん** · 2020/11/08(日) 16:03:50.98

自明なので判定するまでもないが。

**デフォルトの名無しさん** · 2020/11/08(日) 16:28:09.83

データ構造とアルゴリズムって人気ないの？

**デフォルトの名無しさん** · 2020/11/29(日) 20:21:41.24

これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが
もう少しどなたか詳細に解決して頂けないでしょうか。

https://codility.com/media/train/7-MaxSlice.pdf

**デフォルトの名無しさん** · 2020/11/29(日) 21:27:01.68

dpテーブル作って考えたほうがわかりやすいと思います
https://www.nii.ac.jp/userdata/shimin/documents/H22/100805_3rdlec.pdf
これの19ページとか

**デフォルトの名無しさん** · 2020/11/29(日) 21:37:18.71

そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです．

max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
であると仮定する．

max_ending = max(0, max_ending+a)
を実行した後，
max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
が成り立つ．

**デフォルトの名無しさん** · 2020/11/29(日) 22:05:05.40

5, -7, 3, 5, -2, 4, -1

インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceは，3, 5, -2, 4です．

インデックスが6で終わるsliceまたは空のsliceのうち，その和が最大であるsliceをSとする．
Sは何になるか？
3 + 5 - 2 + 4 - 1 = 9 > 0なので，Sは空のsliceではありません．

Sは，例えば，5, -2, 4, -1ではありません．もし，Sが，5, -2, 4, -1であるとすると，
5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって，
5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく，
5, -2, 4であるということになってしまうからです．

Sは，例えば，-7, 3, 5, -2, 4, -1ではありません．もし，Sが，-7, 3, 5, -2, 4, -1であるとすると，
-7 + 3 + 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって，
-7 + 3 + 5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく，
-7, 3, 5, -2, 4, -1であるということになってしまうからです．

**デフォルトの名無しさん** · 2020/11/29(日) 23:01:49.05

>>13
これ最初から足していってマイナスになったらリセットしてまた足し始める
それまでの最大を超えたら最大値を更新するってだけじゃないの
マイナスになったらそれを足し続けても得しないって訳だから

**デフォルトの名無しさん** · 2020/11/29(日) 23:10:03.18

そうですね．
足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね．

**(u＿・y)** · 2020/11/30(月) 17:46:41.21

そうですよ。マイナスでさえなければ、いないよりはマシだから、あなたも雇われ続けているんです。
さらに2 + 2は必ずしも4ではなく、2 +2 = 80にもなるんです。

**デフォルトの名無しさん** · 2020/12/03(木) 18:30:54.40

>>14
分離定理初めて知った、しゅごい
まあ算術でとかループでとか、ジャンプと変数があればとか、λさえあれば…とか似たような定理は見掛けたけど、は低レベル過ぎて指針にならんからな
これらでできないかひとしきり考えてみることにする
(もちろんちゃんと使える演算子は使います)

**デフォルトの名無しさん** · 2020/12/22(火) 15:07:11.40

近似アルゴリズムの本に
極大マッチングは，単に辺を一つずつ選んでいきながら，選んだ辺の両端点とそれらに接続するすべての辺を除いて辺がなくなるまで繰り返すことで得られる
とあり，nを頂点の数，mを辺の数としたとき，計算時間がO(n + m)と書いてあるのですが
nはどこから来たのでしょうか
両方に点が残っている辺を見ていけばいいのでO(m)でできると思うのですが

**デフォルトの名無しさん** · 2020/12/31(木) 21:02:35.54

ArrayListって実装的にはただの可変長配列ですか？

**デフォルトの名無しさん** · 2021/01/01(金) 06:52:59.87

>>16
これは、最大連続区間か？

**デフォルトの名無しさん** · 2021/02/27(土) 15:27:53.95

ウィキペディアの焼きなまし法
https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95

にある擬似コードの
if nextE < bestE then
の部分はもしかして間違ってたりします？
この評価だとnextEが悪化するたびbestが更新されるように見えますが

**デフォルトの名無しさん** · 2021/02/27(土) 16:54:14.85

小さい方が良いでしょ

**デフォルトの名無しさん** · 2021/02/27(土) 16:54:38.59

値が小さい方が望ましい

**デフォルトの名無しさん** · 2021/02/27(土) 17:10:02.18

よく読んでなかったすまんかった

**デフォルトの名無しさん** · 2021/03/08(月) 16:54:28.07

焼きなましに例えるんだからEnergyのEだろうね
線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価)
シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気
LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば
実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価

**デフォルトの名無しさん** · 2021/03/17(水) 19:38:57.60

初歩的な質問かもしれず、恐縮ですがお願いいたします。

i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。
最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。
ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。

もし分かる方がおられましたら、ご助言いただると幸いです。
よろしくお願いします。

**デフォルトの名無しさん** · 2021/05/19(水) 16:18:22.70

Minimum Mean Cycleでこのスライドを見ているのですが
3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？
http://www.columbia.edu/~cs2035/courses/ieor6614.S16/mmc.pdf

(d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね
d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか

**デフォルトの名無しさん** · 2021/05/22(土) 02:18:16.19

>>29
取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ

**デフォルトの名無しさん** · 2021/10/03(日) 17:59:42.80

幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？
Nは頂点の数、Eは辺の数です。

**デフォルトの名無しさん** · 2021/10/03(日) 20:36:41.51

辺の数だけ処理が増えるから
頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる

**デフォルトの名無しさん** · 2021/10/03(日) 22:55:23.59

モートン順序によって当たり判定を一瞬で計算するというのがありました

あれ特定の境目の上にオブジェクトがあるとすべてのオブジェクトとの衝突判定が発生するんですが
世の中のゲームってそんなふうにやってるんですか

**デフォルトの名無しさん** · 2021/10/04(月) 18:40:34.82

計算量がO(V + E)であるの定義は何ですか？

**デフォルトの名無しさん** · 2021/10/04(月) 22:35:12.16

それは計算量の定義をきいているのか？

**デフォルトの名無しさん** · 2021/10/05(火) 00:11:45.95

そのアルゴリズムの計算時間を f(n) とし、オーダーが O(g(n)) と表記される場合、定数cがあって、n がある程度大きくなれば常に f(n) <= c * g(n) が成り立つ。言い方を変えれば計算時間は最悪のケースでも c * g(n) を超えない

g(n) が N (Nの1次式) なら計算時間は c * N を超えないし
g(n) が N^2 (2次式) なら c * N^2 を超えない

c はマシンのスペックや環境で変わるので具体的な数値は追求しない
Nの入力サイズが10倍、100倍、...、1万倍となったときに計算時間がおおよそどのくらいのスピードで増えるか見積もれれば良い
O(N) なら10倍、100倍、...、1万倍
O(N^2) なら100倍、1万倍、...、1億倍..

詳しくはアルゴリズムの教科書か
https://ja.wikipedia.org/wiki/ランダウの記号

**デフォルトの名無しさん** · 2021/10/05(火) 02:13:06.84

>>37
ありがとうございます。
ですが、O(V + E)の中に書かれている式であるV + Eは2変数の関数です。それでも1変数の場合と同じ定義でいいんですか？

**デフォルトの名無しさん** · 2021/10/05(火) 03:31:33.71

>>38
定義は同じ
V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される
E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ
合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる

**デフォルトの名無しさん** · 2021/10/05(火) 08:50:55.08

>>39
なるほど。ありがとうございました。

**デフォルトの名無しさん** · 2021/10/10(日) 18:05:52.24

以下のプログラミングコンテストの問題なのですが、『アルゴリズム実技検定』という本の解説では、これは動的計画法の問題であると書いてあります。
本当にこういうのも動的計画法と言いますか？

https://atcoder.jp/contests/abc026/tasks/abc026_c

**デフォルトの名無しさん** · 2021/10/10(日) 19:42:09.58

>>41
ツリーを作って再帰にもできそうだけど、番号の1番大きい社員から少ない社員に向かって1つずつ処理していけば動的計画法になるね

最初に各社員に部下の給料のリスト（最初は空）を持たせて、社員番号Nから2番に向かって部下の給料のリストに値があればそこから自分の給与を計算して上司のリストに加えることを繰り返す
社員N番を含めて部下がいない、自分の番が回ってきても部下の給料リストが空なら1を上司のリストに加えればいい

**デフォルトの名無しさん** · 2021/10/10(日) 20:02:45.11

部下の給与リストじゃなくて最大値と最小値だけ覚えとけばもっと賢いか

**デフォルトの名無しさん** · 2021/10/10(日) 20:08:58.53

>>42-43
ありがとうございました。

『アルゴリズム実技検定』では、上司部下の関係を親子の関係と考えたツリーを考えて、再帰を使った深さ優先探索のような処理をしています。
そして、そのプログラムを動的計画法を使ったプログラムと書いています。

**デフォルトの名無しさん** · 2021/10/10(日) 22:19:32.54

英語版Wikipedia（その出展として挙げられている『アルゴリズムイントロダクション』）の説明に従うと、この例は部分問題重複性が無いので、動的計画法ではなく分割統治アルゴリズムと呼ぶべきでしょうね
https://en.m.wikipedia.org/wiki/Dynamic_programming

競技プログラミング界隈だとこのような例も動的計画法と呼ぶ人はいますが、書籍でそれが一般的であるかのように書かれているのはあまりよくないように思えますね

**デフォルトの名無しさん** · 2021/10/10(日) 22:22:05.61

>>45
ありがとうございました。

**デフォルトの名無しさん** · 2021/10/11(月) 16:16:04.73

閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。

AtCoderの出題ページは以下になります。
https://atcoder.jp/contests/dp/tasks/dp_g

『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。
私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。
本当に「トポロジカルソート」というのが必要でしょうか？

なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」
と書いています。

『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。
つまり「トポロジカルソート」など不要ではないかと思うんです。

以下がジャッジにパスした私のPythonのコードです。

https://ideone.com/iQIvcc

**デフォルトの名無しさん** · 2021/10/11(月) 16:25:53.01

>>47
あともう一点。
この問題の出題カテゴリは動的計画法に属します。
『アルゴリズム実技検定』の模範解答も私のコードも、深さ優先探索 + 「メモ化再帰」で答えを計算しています。

>>45
確かにこの問題の場合部分問題重複性はあると思いますが、こういう単なる、いわゆる「メモ化再帰」も動的計画法と言っていいのでしょうか？

**デフォルトの名無しさん** · 2021/10/12(火) 00:41:32.76

まず、動的計画法の実現方法にはトップダウン方式とボトムアップ方式があり、メモ化再帰はトップダウン方式の実現方法に当たります
こちらは日本語版のWikipediaにも記載があります
https://ja.m.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95

トポロジカルソートの知識が必須になるのは、ボトムアップ方式で実現する場合です

メモ化再帰する場合にはトポロジカルソートを意識する必要はありません
ここで行われているメモ化再帰の実装は、深さ優先検索を用いたトポロジカルソートの実装と類似しており、結果的にトポロジカルソートの逆順で計算結果が確定されていくことになります

**デフォルトの名無しさん** · 2021/10/12(火) 07:51:06.12

>>49
ありがとうございました。

『アルゴリズム実技検定』でのコードは、トップダウン方式ですので、「トポロジカルソート」などという言葉を出さなくても良かったわけですね。

**デフォルトの名無しさん** · 2021/10/15(金) 14:52:49.77

https://atcoder.jp/contests/past201912-open/tasks/past201912_i

↑の問題を↓のように解きました。

https://ideone.com/osdCtN

コメントアウトしている行をアンコメントするとジェッジにパスしなくなります。
理由が分かりません。
理由が分かる方、教えて下さい。

**デフォルトの名無しさん** · 2021/10/15(金) 15:11:44.64

あ、わかりました。

**デフォルトの名無しさん** · 2021/10/15(金) 15:13:27.96

よかったね、さようなら

**デフォルトの名無しさん** · 2021/10/24(日) 20:12:12.31

https://atcoder.jp/contests/past202004-open/tasks/past202004_f

この問題は貪欲法が適用できるとのことですが、適用できることの証明はどう証明するのでしょうか？

**デフォルトの名無しさん** · 2021/10/24(日) 22:55:10.72

>>54
k日間で得られるポイントの合計の最大値を P(k) と表し、k日目に解禁されるタスクが2つあってそれぞれのポイントを p, q (p < q) とする。

貪欲法でないやり方で求めた最適解P(k)*があるとする。--- (1)
貪欲法でないある方針に基づいてpポイントのタスクを選択したとする。

このとき、貪欲法に基づいてqポイントのタスクを選択したとすると、P(k) = P(k)* + q - p となる更に良い解が得られ、(1) の「貪欲法でなくても最適解」の前提条件に矛盾する。

毎回思うけどこの atcoder てあんまり良くないね。
日本語の問題文があるから重宝されてるのかもしれないけど、入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり、解説ないからもっと良い解があるのかわからないし、leetcode あたりのが勉強になると思う。

**デフォルトの名無しさん** · 2021/10/25(月) 11:24:00.83

まるちんこ

**デフォルトの名無しさん** · 2021/10/25(月) 12:10:28.14

以下のような感じで証明できないですかね？

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {(S_1, S_2, …, S_k) | 1 ≦ k ≦ n, S_i は第i日に行うタスク, p(S_1 + … + S_k) > p(T_1 + … + T_k)}

S が空集合ではないとして矛盾を導く。

(S_1, S_2, …, S_l) を長さが最小の S の元とする。

p(S_1) + … + p(S_{l-1}) ≦ p(T_1) + … + p(T_{l-1})

**デフォルトの名無しさん** · 2021/10/25(月) 16:58:37.64

Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。

**デフォルトの名無しさん** · 2021/10/26(火) 11:19:31.94

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。

k_0 := min S とおく。

第1日目から第k_0日目の間に得られるポイントの合計の最大値を達成するタスク列を

S_1, S_2, …, S_{k_0} とする。

仮定により、

p(S_1) = p(T_1)
p(S_2) = p(T_2)
…
p(S_{k_0-1}) = p(T_{k_0-1})
p(S_{k_0}) > p(T_{k_0})

が成り立つ。

**デフォルトの名無しさん** · 2021/10/26(火) 11:33:36.58

このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で

p(R_{k_0}) = p(T_{k_0})
p(R_{k_0+1}) = p(T_{k_0+1})
…
p(R_{n}) = p(T_{n})

を満たすようなものが存在することは明らかである。

このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。

ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、
タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。

これは矛盾である。

よって、 S は空集合である。

**デフォルトの名無しさん** · 2021/10/31(日) 19:17:33.86

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？

ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？

**デフォルトの名無しさん** · 2021/11/02(火) 10:37:08.97

>>61
https://www.youtube.com/watch?v=SsB8VfxgZwQ

**デフォルトの名無しさん** · 2021/11/02(火) 13:38:39.49

『Introduction to Algorithms 3rd Edition』よりも『Algorithm Design』のほうがずっといい本だと思うのですが、どうですか？

**デフォルトの名無しさん** · 2021/11/03(水) 18:42:32.00

https://i.imgur.com/EqwQfdx.jpg

↑は、Dijkstraのアルゴリズムの擬似コードですが、これって間違っていますよね？

Sに付け加えられるvに対してのみd[v]を計算しています。

**デフォルトの名無しさん** · 2021/11/03(水) 19:10:00.22

追加される時点で最短距離が決定するから問題ないと思うが。

**デフォルトの名無しさん** · 2021/11/03(水) 19:38:24.24

>>65
ありがとうございました。
あ、d'[v]のほうは更新され続けるんですね。
そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。
dなんて使わずにd'だけでいいのにと思います。

**デフォルトの名無しさん** · 2022/03/05(土) 12:18:28.50

https://i.imgur.com/SLWsXcA.jpg

**デフォルトの名無しさん** · 2022/03/05(土) 18:15:22.85

>>67
グロ

**デフォルトの名無しさん** · 2022/04/09(土) 22:56:02.65

頭では分かってるつもりなんだけど
どうしても実際にはif , switchのオンパレードになっちゃんだよな

特に仕事だと、学術論的なことでぐずぐずハマってたら
なにやってんだってはなしになることが多い

**デフォルトの名無しさん** · 2022/08/31(水) 20:45:30.79

『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．

https://atcoder.jp/contests/dp/tasks/dp_g

解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．

**デフォルトの名無しさん** · 2022/08/31(水) 20:52:44.34

解答は以下のような感じです：

length(v)を点vからの最長パスの長さとします．

v → w_1
v → w_2
…
v → w_n

という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）

この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．

**デフォルトの名無しさん** · 2022/08/31(水) 20:55:47.47

入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．

**デフォルトの名無しさん** · 2022/08/31(水) 20:58:25.24

https://ideone.com/LvMx0h

例えば，上のプログラムのような感じです．

**デフォルトの名無しさん** · 2022/09/01(木) 09:35:46.60

入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい

**デフォルトの名無しさん** · 2022/09/04(日) 06:43:45.43

でもトポロジカルソートしていないですよね．プログラムを見ると．

**デフォルトの名無しさん** · 2022/09/18(日) 14:40:45.95

C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、
削除したい要素を探すのにO(N)必要だと思います。

これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？