[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
240: 2023/12/22(金)02:09 AAS
LCAライブラリをいじる手間を考えるとセグ木DFSのほうが実装楽そう
クエリ対応のLCA持ってないし
241(1): 2023/12/22(金)02:18 AAS
>>238
似たようなこと考えてたけど、セグ木じゃなくてmultisetでシミュするだけで良さそうだと思った
242: 2023/12/22(金)02:19 AAS
>>238,241
ごめん、LCAの上の爺も残るので嘘でした
243: 2023/12/22(金)02:32 AAS
良質スレがよぉ
244: 2023/12/22(金)02:33 AAS
過去スレ精進しろ(ガチ)
245: 2023/12/22(金)02:37 AAS
スレ精進がほんとに競プロの精進を兼ねる日が来るとはな
246(1): 2023/12/22(金)03:04 AAS
木の問題、クエリ先読み→並列二分探索でも解けそう
O((Q+N) log N α(N)) くらいで
247: 2023/12/22(金)03:13 AAS
>>246
詳細：
部分問題：K を固定する. u,v を結ぶパスの頂点の中に重み K 以下のものがあるか？
という問題は頂点∪{K}を重み順にソートして, UnionFind で頂点重み大きい順からマージしていくと, いい感じのところで（だいたい）連結か非連結かで判定できる
これは Q 個のクエリに同時に行うこともできる. Q 個のクエリの K の最小値がすべて定まるまで繰り返せばよいが, O(log N) 回におさまる
248: 2023/12/22(金)03:32 AAS
マージテクで解けそうじゃね
N-1本の辺にmax(Ai, Aj)のコストを割り振り、コストの昇順にソート
これで「初めてクエリの頂点対が連結になったのはいつ？」という問題に帰着する
各連結成分ごとに連想配列で(クエリの対となる頂点番号、クエリ番号)を保持しておく
辺を追加すると連結成分のマージが発生するが、連結成分数が大きい方から小さい方に連想配列の照会を行う（つまり、クエリの対となる頂点がいるか確認する）
ここではじめて連結になるクエリ対がいれば、このときの追加辺コストが答え
最後に連想配列のマージを行う
省1
249: 2023/12/22(金)03:37 AAS
深夜にしょーもなバグ見つけて発狂
AC射精完了させてくれよお
250(1): 2023/12/22(金)03:47 AAS
辺の追加順は重みの降順だし
辺のコストはmin(Ai,Aj)だし
ガバガバ
並列二分探索がよく分からんが
ひとつのUnionFind木をlogQ回構築する方針でいいのか？
1回目は全クエリ50%構築地点、2回目は25%地点の判定をしてから構築進めて75%点の判定をする感じ
251: 2023/12/22(金)03:49 AAS
並列二分探索これには適用できなくね？
252(2): 2023/12/22(金)03:55 AAS
>>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
省1
253: 2023/12/22(金)03:57 AAS
並列二分探索適用できないマジ？眠すぎるから自分の頭がバグってるだけかもしれない
254: 2023/12/22(金)04:02 AAS
並列二分探索無理なのなんで？
辺の重みをmin(Ai,Aj)として、辺をコストの降順に追加する。2点(i,j)が連結となるコストのギリギリ上限を求めよ。
という問題に読み替えられるだろ
クエリが1個なら解の二分探索ができて
辺を降順にM個追加したとき、2点(i,j)は連結か？
という判定問題をO(logN)回解けばいい
単純なUFはundo不可能だから毎回UFを1から構築し直す必要があり、1クエリあたりO(Nα[N]logN)かかる
省2
255(1): 2023/12/22(金)04:04 AAS
>>252
合っててよかった
計算量にlog^2の項は生えないはず 辺の重みソートは初回だけでよいので
256: 252 2023/12/22(金)04:07 AAS
>>255
たしかに
サボらずにちゃんとやればソートでかかる log は落ちるか（自分はめんどくさくて生やしてしまいそう）
257: 2023/12/22(金)04:07 AAS
なんでこんなガイジスレで真面目なUF解法を2個も生やさねばならんのだ
258: 2023/12/22(金)05:36 AAS
競プロで磨いた実装力🤓で重めのアルゴリズム実装課題数時間でシバいといた
259: 2023/12/22(金)05:52 AAS
並列二分探索、こどふぉではまあまあ見かけるけどあとこでは全然見かけない気がする
ABCに並列二分探索想定の問題あったっけ？
260: 2023/12/22(金)06:10 AAS
ガイジスレ終了
261: 2023/12/22(金)06:19 AAS
AC～😎
262: 2023/12/22(金)08:34 AAS
全然無いな
ABC233Exの想定解
ABC234Dの別解
263: 2023/12/22(金)08:34 AAS
PASTは第二回の最終問が並列二分探索かLCAか選べたはず
264(1): 2023/12/22(金)09:09 AAS
マージテクの方、マージする際に小さい方から大きい方の連想配列に照会する、じゃないとO(NQ)になるのでは
265: 2023/12/22(金)09:29 AAS
>>264
想定は連想配列もマージしていた
連想配列をマージしていれば、大→小のアクセス回数が小集合の頂点数と等しくなる
計算量は各頂点ごとの「照会を受ける回数」を考えれば全体でO(NlogN)
連想配列のマージはよくあるクエリ数の大←小のマージでよくて全体でO(QlogQ)
連想配列をマージしない場合、二乗の木DPみたいにO(N^2)かかりそうじゃない？
266(2): 2023/12/22(金)10:14 AAS
多分頭にあるのは同じアルゴリズムなんだけど、用語の使い方の感覚が違うというだけな気がする
大きい方から小さい方に照会を行うと言われると、大きい方の連想配列のkeyを全部取り出して、小さい方の連想配列内に存在するか否かを判定しているように聞こえた
俺がいいたかった「小さい方から大きい方に照会する」というのは
for query_key in small:
if query_key in big:
process(query_key) # 初めてquery_keyの２頂点が連結したと判定
else:
省4
267: 2023/12/22(金)10:16 AAS
>>266
５行目はsmall.add(query_key)じゃなくて、big.add(query_key)
268(1): 2023/12/22(金)10:24 AAS
あ、smallとbigはPythonのset(C++でいうところのstd::set)ね
269: 2023/12/22(金)10:25 AAS
>>268
std::unordered_setだわ
5chも真面目な話したいときは普通にレス修正機能ほしいな
270: 2023/12/22(金)10:29 AAS
デアをやるガイジスレーラ好きだ！！！！
271: 2023/12/22(金)10:36 AAS
>>266
ぜんぜん違うアルゴリズムだった
そっちのほうが綺麗だわ
恥晒ししとくと、G[集合A][頂点i] = [クエリx, クエリy, …]
みたいな集合と頂点の隣接辞書を考えてた
無駄にO(NlogN)が生えるゴミなので忘れてください
272(1): 2023/12/22(金)11:24 AAS
いずれにせよ頂点もクエリもどちらもマージする必要があるから、どうしてもO(NlogN+QlogQ)にはなると思う
結果的にはあんま変わらないかと
というか、クエリのhashsetをマージする際には連結成分成分の大小じゃなくて、hashsetの大小で考える必要があるな
273(1): 2023/12/22(金)11:26 AAS
>>272
てレスしながら、頂点側のマージ要らない気もしてきたわ
まあどうせソートで結局O(NlogN+QlogQ)
274(1): 2023/12/22(金)11:38 AAS
【低収入】派遣スキルつけるな【低技術】
☆大迷惑だから稼働減らして収入増やせ☆
偽装委託多重派遣の開発料金詐欺被害者の作業
[文系多数の貧困非婚スキル]
コマンド
スクリプト
データ > ロジック
省21
275: 2023/12/22(金)11:41 AAS
>>274
転職のためだけに水とか青とかやってられんでしょ
やはり社会に求められているのはpaiza
276: 2023/12/22(金)11:46 AAS
>>237
そう、頂点の管理が要らないからクソ強い解法
クエリのババ抜きだけやればいい
277: 2023/12/22(金)11:46 AAS
>>273だわ
278(1): 2023/12/22(金)11:48 AAS
頂点側はマージ要らないってUFなりで管理するということ？マージテクが要らないという意味？
279(1): 2023/12/22(金)11:54 AAS
集合と頂点の対応関係が分からない場合の辺追加クエリ
280: 2023/12/22(金)12:00 AAS
>>278,279
要るわすまん
UFなりなんなりで管理しないと辺が追加できない
281: 2023/12/22(金)12:11 AAS
マージテクが要らないから計算量落ちてO(Nα(N)+QlogQ)という感じか
282: 2023/12/22(金)12:21 AAS
逆にO(Q(logN)^2)かかるHL分解は何が嬉しいのかって考えたらオンラインクエリに対応できるのか
世の中上手くできてんなあ
283(1): 2023/12/22(金)12:28 AAS
父と母のマージテクで生まれてきました🤓
284(1): 2023/12/22(金)12:37 AAS
マージテクの小さい方から挿れるって部分直感に反する
285(1): 2023/12/22(金)12:54 AAS
284のせいでややセックスの話に見える
286: 2023/12/22(金)13:29 AAS
AC射精完了
287: 2023/12/22(金)13:30 AAS
えっち始まってた、いっつも夕方くらいのイメージだったが早いな
というか1週間無いのか～えっち短いな
288: 2023/12/22(金)13:42 AAS
>>283,284,285
かけ算の順序、足し算の順序と考えればそんなにエロくない
書いてて気づいたが遺伝子の交配ってベクトルの積の1種か
289: 2023/12/22(金)13:48 AAS
性欲erもちゃんとデ・アの話をしていたというわけか
290: 2023/12/22(金)13:54 AAS
性欲erの場合はデ・ア厨じゃなくて出会い厨だぞ
291: 2023/12/22(金)15:14 AAS
強化学習ってどうやるんだ
292: 2023/12/22(金)15:36 AAS
なんか変なレート遷移のやつおって草
外部ﾘﾝｸ:atcoder.jp
293(1): 2023/12/22(金)15:38 AAS
どうなってんだこれ
おそらく普通に強い人だと思うんだけど何が目的なんだ
外部ﾘﾝｸ:codeforces.com
294(1): 2023/12/22(金)15:42 AAS
codeforcesって自由色はないよな？
だとしたらバグってない？
外部ﾘﾝｸ:codeforces.com
画像ﾘﾝｸ[jpg]:i.imgur.com
295(1): 2023/12/22(金)15:43 AAS
>>293
新参の寒色インコだろお前
rainboyは後ろから解くことで超有名だぞ
296: 2023/12/22(金)15:44 AAS
まーたゴシップか
レート的実体のある話だけに如何ともし難いが
297: 2023/12/22(金)15:44 AAS
>>294
新参の寒色インコだろお前
こどふぉはクリスマスだか年末年始だかの時期は自由に色変えられるんだぞ(灰色が赤にできたりもする)
298: 2023/12/22(金)15:44 AAS
過去スレ精進していたらそんな恥晒さずに済んだのに...
299: 2023/12/22(金)15:45 AAS
しょうもない質問する前に検索か過去スレ精進くらいはしとけ
300: 2023/12/22(金)15:45 AAS
しょうもないからデ・アの話に戻そう
301: 2023/12/22(金)15:46 AAS
(コドフォの仕様は俺も知らんかったわ...)
302: 2023/12/22(金)15:46 AAS
こどふぉサボるからそうなるんだよFAKE野郎がよ
303(1): 2023/12/22(金)15:49 AAS
>>295
赤色相当の実力はある人なの？
304: 2023/12/22(金)15:51 AAS
こどふぉのレート見てみ
305: 2023/12/22(金)15:51 AAS
>>303
少しはコンテスト履歴とか色々自分で調べてみろよ……(そういうところがインコ仕草すぎる)
IOIに出てたりボス問解けてたりするからこどふぉ赤ならあるんじゃないの
306: 2023/12/22(金)15:52 AAS
寒色インコは検索すら出来ないからな
307: 2023/12/22(金)15:57 AAS
色々と調べて見た感じ、cfだとgrandmaster相当の実力はありそうだから、AtCなら橙～赤くらいの実力かな
308(1): 2023/12/22(金)15:58 AAS
画像1枚うｐするだけにえらい時間かかってるやつもいましたね
309: 2023/12/22(金)15:59 AAS
agerか？なりすましagerのことどう思う？
310: 2023/12/22(金)15:59 AAS
自分の個人情報を晒す可能性のある学生証UPと他人のレートスクショが同じだと思ってるバカ
311: 2023/12/22(金)16:00 AAS
これagerかよ
やっぱり昨日のデ・アの話にはついてこれないから毎回こういう話題持ってくるんだな
312: 2023/12/22(金)16:01 AAS
酉すら知らなかったあたりとかもわりと笑えるし
313: 2023/12/22(金)16:01 AAS
>>308
じゃあお前も学生証うpしたら？
314: 2023/12/22(金)16:01 AAS
agerってなんでこんなに浮いてるんだ
315: 2023/12/22(金)16:03 AAS
agerじゃねぇだろ
多分
316: 2023/12/22(金)16:03 AAS
良スレだったのによぉ
317(1): 2023/12/22(金)16:03 AAS
過去スレを読めば分かるが大したデアの話はしていないため
318: 2023/12/22(金)16:03 AAS
自分の学生証晒す勇気すらない奴が叩くなよ
319(1): 2023/12/22(金)16:04 AAS
>>317
半日前くらいの書き込みみろよ
320: 2023/12/22(金)16:04 AAS
外部ﾘﾝｸ:codeforces.com
並列二分探索のこどふぉ記事貼っておくからお前らagerに構ってないで読んどけよ
上下前次1-新書関写板覧索設栞歴
あと 682 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.013s