[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)

競技プログラミングにハマるプログラマのスレ 143 http://medaka.5ch.net/test/read.cgi/prog/1703141733/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

250: 仕様書無しさん [sage] 2023/12/22(金) 03:47:58.33 辺の追加順は重みの降順だし 辺のコストはmin(Ai,Aj)だし ガバガバ 並列二分探索がよく分からんが ひとつのUnionFind木をlogQ回構築する方針でいいのか？ 1回目は全クエリ50%構築地点、2回目は25%地点の判定をしてから構築進めて75%点の判定をする感じ http://medaka.5ch.net/test/read.cgi/prog/1703141733/250

252: 仕様書無しさん [sage] 2023/12/22(金) 03:55:35.82 >>250 そんな感じになるが、下限と上限の配列 ng(Q), ok(Q) を用意して log N 回行う： 1. 配列 t(Q) を, t[i] = (ng[i] + ok[i]) / 2 で定める 2. t(Q) と頂点を一緒にして重み降順ソートする 3. N 要素の UnionFind を用意する 4. 頂点重みの大きいほうから見ていく, t(Q) の要素にぶつかったら判定 5. i 番目の判定が true なら ok(i) ← t, そうでなければ ng(i) ← t すみませんソートが入るから O((N+Q) log^2 (N+Q)) か http://medaka.5ch.net/test/read.cgi/prog/1703141733/252

---

ﾒﾓ帳

(0/65535文字)

---

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

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.027s