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