データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
1: デフォルトの名無しさん [sage] 2020/01/27(月) 22:28:35.79 ID:yq8WVV9K 【前スレ】 データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 http://mevius.5ch.net/test/read.cgi/tech/1580131715/1
2: デフォルトの名無しさん [] 2020/07/27(月) 12:25:50.05 ID:n24uY58k 深さ優先探索の計算時間がO(|V| + |E|)と評価されるのはなぜですか？ |V| << |E|だから、O(|E|)でOKな気がします。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/2
3: デフォルトの名無しさん [sage] 2020/07/27(月) 12:40:31.34 ID:NergLkg0 わからんけどグラフの連結性を仮定してないのでは http://mevius.5ch.net/test/read.cgi/tech/1580131715/3
4: デフォルトの名無しさん [sage] 2020/07/27(月) 15:17:43.62 ID:BQ7JhCRr >>2 |E| < |V|^2 だぞ http://mevius.5ch.net/test/read.cgi/tech/1580131715/4
5: デフォルトの名無しさん [sage] 2020/09/22(火) 22:37:15.01 ID:Ok4HXOVw ２つの同数の点集合A,Bがあって １対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか 具体的にはa_i∈A, b_j∈B i->j : j(i) Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i) http://mevius.5ch.net/test/read.cgi/tech/1580131715/5
6: デフォルトの名無しさん [sage] 2020/09/22(火) 23:17:08.08 ID:txyi13VO 二部グラフの最小重み完全マッチングでいけないかな http://mevius.5ch.net/test/read.cgi/tech/1580131715/6
7: デフォルトの名無しさん [sage] 2020/09/22(火) 23:22:00.48 ID:txyi13VO でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな それならハンガリアン法とか最小費用流で解けるのでは http://mevius.5ch.net/test/read.cgi/tech/1580131715/7
8: デフォルトの名無しさん [sage] 2020/09/22(火) 23:31:12.82 ID:Ok4HXOVw ありがとうございます 調べてみます http://mevius.5ch.net/test/read.cgi/tech/1580131715/8
9: デフォルトの名無しさん [] 2020/11/08(日) 15:47:31.10 ID:hnEKBOnE 開票所要時間は理論上 O(log n) だよね？ 【米大統領選】日本なら一晩で終わる開票作業 なぜそんなに時間がかかったのか(デイリー新潮) https://news.yahoo.co.jp/articles/e7f705c442fa18c1455c579a7cd209861ef6212b http://mevius.5ch.net/test/read.cgi/tech/1580131715/9
10: デフォルトの名無しさん [sage] 2020/11/08(日) 15:50:45.10 ID:YOqFgelx アルゴリズムで書いたら判定してやるよ http://mevius.5ch.net/test/read.cgi/tech/1580131715/10
11: デフォルトの名無しさん [] 2020/11/08(日) 16:03:50.98 ID:hnEKBOnE 自明なので判定するまでもないが。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/11
12: デフォルトの名無しさん [] 2020/11/08(日) 16:28:09.83 ID:BBDku6LQ データ構造とアルゴリズムって人気ないの？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/12
13: デフォルトの名無しさん [] 2020/11/29(日) 20:21:41.24 ID:rAnHdnpn これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが もう少しどなたか詳細に解決して頂けないでしょうか。 https://codility.com/media/train/7-MaxSlice.pdf http://mevius.5ch.net/test/read.cgi/tech/1580131715/13
14: デフォルトの名無しさん [sage] 2020/11/29(日) 21:27:01.68 ID:exnO589A dpテーブル作って考えたほうがわかりやすいと思います https://www.nii.ac.jp/userdata/shimin/documents/H22/100805_3rdlec.pdf これの19ページとか http://mevius.5ch.net/test/read.cgi/tech/1580131715/14
15: デフォルトの名無しさん [] 2020/11/29(日) 21:37:18.71 ID:M8xgBTYt そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです． max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 であると仮定する． max_ending = max(0, max_ending+a) を実行した後， max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 が成り立つ． http://mevius.5ch.net/test/read.cgi/tech/1580131715/15
16: デフォルトの名無しさん [] 2020/11/29(日) 22:05:05.40 ID:M8xgBTYt 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であるということになってしまうからです． http://mevius.5ch.net/test/read.cgi/tech/1580131715/16
17: デフォルトの名無しさん [sage] 2020/11/29(日) 23:01:49.05 ID:0fgKV2B3 >>13 これ最初から足していってマイナスになったらリセットしてまた足し始める それまでの最大を超えたら最大値を更新するってだけじゃないの マイナスになったらそれを足し続けても得しないって訳だから http://mevius.5ch.net/test/read.cgi/tech/1580131715/17
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 88 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.014s