データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
1: 2020/01/27(月)22:28 ID:yq8WVV9K(1) AAS
【前スレ】
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3
2chｽﾚ:tech
【関連スレ】
3Dアルゴリズム全般
2chｽﾚ:tech
＜集大成＞アルゴリズム大辞典
2chｽﾚ:tech
アルゴリズム総合スレ in ム板
2chｽﾚ:tech
アルゴリズムとデータ構造 - Kaneko Lab.
外部ﾘﾝｸ[html]:www.kkaneko.com
アルゴリズムとデータ構造 - ソースコード探険隊
外部ﾘﾝｸ:www.codereading.com
各種アルゴリズムの C++ による実装 - Spaghetti Source
外部ﾘﾝｸ:www.prefield.com
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
外部ﾘﾝｸ[html]:vipprog.net
2(1): 2020/07/27(月)12:25 ID:n24uY58k(1) AAS
深さ優先探索の計算時間がO(|V| + |E|)と評価されるのはなぜですか？
|V| << |E|だから、O(|E|)でOKな気がします。
3: 2020/07/27(月)12:40 ID:NergLkg0(1) AAS
わからんけどグラフの連結性を仮定してないのでは
4: 2020/07/27(月)15:17 ID:BQ7JhCRr(1) AAS
>>2
|E| < |V|^2 だぞ
5: 2020/09/22(火)22:37 ID:Ok4HXOVw(1/2) AAS
２つの同数の点集合A,Bがあって
１対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか
具体的にはa_i∈A, b_j∈B
i->j : j(i)
Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i)
6: 2020/09/22(火)23:17 ID:txyi13VO(1/2) AAS
二部グラフの最小重み完全マッチングでいけないかな
7: 2020/09/22(火)23:22 ID:txyi13VO(2/2) AAS
でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな
それならハンガリアン法とか最小費用流で解けるのでは
8: 2020/09/22(火)23:31 ID:Ok4HXOVw(2/2) AAS
ありがとうございます
調べてみます
9: 2020/11/08(日)15:47 ID:hnEKBOnE(1/2) AAS
開票所要時間は理論上 O(log n) だよね？
【米大統領選】日本なら一晩で終わる開票作業 なぜそんなに時間がかかったのか(デイリー新潮)
外部ﾘﾝｸ:news.yahoo.co.jp
10: 2020/11/08(日)15:50 ID:YOqFgelx(1) AAS
アルゴリズムで書いたら判定してやるよ
11: 2020/11/08(日)16:03 ID:hnEKBOnE(2/2) AAS
自明なので判定するまでもないが。
12: 2020/11/08(日)16:28 ID:BBDku6LQ(1) AAS
データ構造とアルゴリズムって人気ないの？
13(1): 2020/11/29(日)20:21 ID:rAnHdnpn(1) AAS
これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが
もう少しどなたか詳細に解決して頂けないでしょうか。
外部ﾘﾝｸ[pdf]:codility.com
14(1): 2020/11/29(日)21:27 ID:exnO589A(1) AAS
dpテーブル作って考えたほうがわかりやすいと思います
外部ﾘﾝｸ[pdf]:www.nii.ac.jp
これの19ページとか
15: 2020/11/29(日)21:37 ID:M8xgBTYt(1/3) AAS
そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです．
max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
であると仮定する．
max_ending = max(0, max_ending+a)
を実行した後，
max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
が成り立つ．
16(1): 2020/11/29(日)22:05 ID:M8xgBTYt(2/3) AAS
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であるということになってしまうからです．
17: 2020/11/29(日)23:01 ID:0fgKV2B3(1) AAS
>>13
これ最初から足していってマイナスになったらリセットしてまた足し始める
それまでの最大を超えたら最大値を更新するってだけじゃないの
マイナスになったらそれを足し続けても得しないって訳だから
18: 2020/11/29(日)23:10 ID:M8xgBTYt(3/3) AAS
そうですね．
足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね．
19: (u＿・y) 2020/11/30(月)17:46 ID:nGWGFXsH(1) AAS
そうですよ。マイナスでさえなければ、いないよりはマシだから、あなたも雇われ続けているんです。
さらに2 + 2は必ずしも4ではなく、2 +2 = 80にもなるんです。
20: 2020/12/03(木)18:30 ID:Fq1nYucp(1) AAS
>>14
分離定理初めて知った、しゅごい
まあ算術でとかループでとか、ジャンプと変数があればとか、λさえあれば…とか似たような定理は見掛けたけど、は低レベル過ぎて指針にならんからな
これらでできないかひとしきり考えてみることにする
(もちろんちゃんと使える演算子は使います)
21: 2020/12/22(火)15:07 ID:h5DFCbD/(1) AAS
近似アルゴリズムの本に
極大マッチングは，単に辺を一つずつ選んでいきながら，選んだ辺の両端点とそれらに接続するすべての辺を除いて辺がなくなるまで繰り返すことで得られる
とあり，nを頂点の数，mを辺の数としたとき，計算時間がO(n + m)と書いてあるのですが
nはどこから来たのでしょうか
両方に点が残っている辺を見ていけばいいのでO(m)でできると思うのですが
22: [age] 2020/12/31(木)21:02 ID:pjMyqahK(1) AAS
ArrayListって実装的にはただの可変長配列ですか？
23: 2021/01/01(金)06:52 ID:L8CQYPdE(1) AAS
>>16
これは、最大連続区間か？
24: 2021/02/27(土)15:27 ID:cGuo4IiQ(1/2) AAS
ウィキペディアの焼きなまし法
外部ﾘﾝｸ:ja.wikipedia.org
にある擬似コードの
if nextE < bestE then
の部分はもしかして間違ってたりします？
この評価だとnextEが悪化するたびbestが更新されるように見えますが
上下前次1-新書関写板覧索設栞歴
あと 81 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.006s