データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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)でできると思うのですが