[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
201: 2023/12/22(金)00:31 AAS
>>199
ど直球のラグランジュ補完やるだけの問題だからネタバレしちゃうけど、これとか(上で言ってた試験管橙diff)
外部ﾘﾝｸ:atcoder.jp
202(1): 2023/12/22(金)00:33 AAS
多項式じゃないだけでオーバーシュートして使い物にならない補完くん
203: 2023/12/22(金)00:33 AAS
ABCWriterもよくやってるNyaanさんはFPSかなり好きだから、FPSがより普及したらこの程度のやるだけ問題はそのうちABC-Fで出てもおかしくなさそう(前提知識がなくても解けるとは思うし)
204: 2023/12/22(金)00:35 AAS
マスさんの実績を調べてたらマスさんアンチ湧いててくっそわろた
アンチの内容も難癖つけるだけで更にわろたわ
嫉妬してるんだろうな
205: 2023/12/22(金)00:35 AAS
ヒュ精進、わからんよな（AHCで1から強くなった人間がまだほとんどいないため）
206: 2023/12/22(金)00:36 AAS
行列木定理が好きなwriterいたよな
207: 2023/12/22(金)00:36 AAS
マスさんレベルの天才紹介なら歓迎するのにね
208: 2023/12/22(金)00:38 AAS
ratism精神を全面に押し出す(インコ人間境界線など)ことでスレ全体のレートを上げようとするのも良かったけど、この真面目にデ・アの話をする方向性でスレが安定したら本格的ににスレ民の平均レートが高くなりそう
209: 2023/12/22(金)00:39 AAS
インコ総活躍社会を目指して、世界の天才競プロer紹介みたいな職でagerを再雇用してもいいけど、本人がやる気ないからどうしようもない
210: 2023/12/22(金)00:39 AAS
行列木定理は初めて知った時感動した
最初に発明したやつ凄すぎる
211: 2023/12/22(金)00:42 AAS
へへ...照れるやい！
212: 2023/12/22(金)00:42 AAS
>>202
逆に次数が小さく抑えられるような多項式を相手にすると汎用的でかなり強い
213: 2023/12/22(金)00:43 AAS
過去スレ精進がスレレートを上げる以外にも有効になる日も近い
214: 2023/12/22(金)00:43 AAS
そのうち競プロの解説リンクにガイジスレが貼られるかも
215: 2023/12/22(金)00:44 AAS
元からAtCoder非公式最有力フォーラムなのではい
216: 2023/12/22(金)00:45 AAS
昔は貼られてたのによお
217: 2023/12/22(金)00:46 AAS
nimさんだけじゃなくて社長も宣伝してくれよな
218(1): 2023/12/22(金)00:46 AAS
お前らデ・アの話しろよ、みたいなレスよくあるけどそういうレスしなくても何でもいいから話題さえ提供すれば勝手にそういう流れになりそう
219: 2023/12/22(金)00:47 AAS
UTの赤コーダーが１年生くらいのときに「競技プログラミングと線形代数」みたいなのを(texとかではなくコピー用紙に)書いたpdfで行列木定理とかその他諸々が紹介されてたよな
220: 2023/12/22(金)00:48 AAS
>>218
それな
本当に競プロをやってる(真の意味でのやってる)ならば、こういう話応えのある話題が提供されれば反応するはずだからな
221: 2023/12/22(金)00:49 AAS
安定のでぐわ
222(1): 2023/12/22(金)01:09 AAS
問題作ったけど多分出せるとこないから誰か解いて
各頂点に整数A_iが書かれたN頂点の木に対して、以下の形式のクエリがQ個与えられるのでそれぞれ答えよ。
・頂点u, vを結ぶパス上の頂点iに対して、A_iの最小値を求めよ。
【入力】N, Q, A_i, 辺の情報, 各クエリの2頂点
【制約】N, Q ≦ 10^5, A_i ≦ 10^9
HL分解はオーバーキル&俺が知らないからNG
223(2): 2023/12/22(金)01:15 AAS
>>222
HL分解を知らないならオイラーツアーをやればいいじゃない(DFS順に頂点を並べるだけ)
オイラーツアーを最小値取得セグ木に載せてAC射精完了
やるだけだしABC-Fで水〜青くらいかな
224(2): 2023/12/22(金)01:16 AAS
オフラインなら各クエリのLCAを前計算
minセグ木を一個持ってdfs
225: 2023/12/22(金)01:22 AAS
>>223
>>224
概ね伝わったから正解
こういうシンプルな問題を考えるのが好きなんだけど無限に既出で泣ける
ちな水インコ
226(1): 2023/12/22(金)01:25 AAS
オイラーツアーでパスクエリって処理できたっけ
227: 2023/12/22(金)01:29 AAS
>>226
マス様がオイラーツアーの記事書いてくれてたはず
228(1): 2023/12/22(金)01:33 AAS
もしかして>>223と>>224は違う解法なのか
一応ちゃんと想定通りに伝わったのは>>224のほう
229: 2023/12/22(金)01:33 AAS
普通のやり方だと群じゃないとダメじゃね？
230: 2023/12/22(金)01:39 AAS
>>228
すまん、パスクエリをHL分解じゃなくてオイラーツアーで処理したことがあまりなかったから適当に答えてしまった(1ペナ)
部分木クエリと混同してたけど、最小値はそのままやるだけだと逆元がないからダメっぽいから224みたいにオフラインにして探索順を工夫してまとめてやるしかなさそう
外部ﾘﾝｸ:maspypy.comのお勉強
231: 2023/12/22(金)01:42 AAS
LCAが素直かな
クエリ先読みDFSでも解けないことはなさそうだけど、多分超激重実装になるし、どこかでLCAが必要になる気がする（ので本末転倒）
232: 2023/12/22(金)01:46 AAS
オイラーツアーってDFS探索自体を指すような語感もなくはない（競プロ文脈ではテーブル作成まで包含することがほとんどだと思うが）から紛らわしいところがある
233: 2023/12/22(金)01:47 AAS
最小共通祖先が既に分かっているなら、頂点u,vへのパス上のminAiを逐次計算すればO(N+Q)
でもLCA求めたついでにクエリをダブリング処理するO((N+Q)logN)で絶対によいため
LCAってO(N+Q)で求める方法あるっけ？
234: 2023/12/22(金)01:56 AAS
少し考えたらありそうだけど、重実装なのは変わらんな
1回目のDFSは頂点ごとにクエリを持ち帰って、同じクエリが合流した頂点をLCAとすればO(N+Q)でLCAが求まる
2回目のDFSはLCA→u, LCA→vのminAiを求めればよく、1回目のDFSが書ける人なら当然これも書ける
最後にLCA→u,vの結果を合成して出力すれば合計でO(N+Q)
235: 2023/12/22(金)01:58 AAS
minに逆元がないので嘘だわこれ
2回目のDFSがO(NQ)になるな
236: 2023/12/22(金)02:00 AAS
モノイドがよぉ
237(1): 2023/12/22(金)02:01 AAS
HL分解でいい感じにクエリ辺りの計算回数をlog回に落とすのが定番だけど、こういう解法を考えるのに意味はありそうではある
238(2): 2023/12/22(金)02:01 AAS
一応ちゃんと想定を書く
各クエリをLCAで2つのパスに分解して、子孫のほうに情報を持たせておく。
そしてminセグ木を一つ持って、dfs順に頂点iを走査しセグ木の要素をA_iに更新する（このときのセグ木のインデックスは頂点iの根からの距離）。すると、iの祖先が根から順番にセグ木に並んでいる状態になるので、iに持たせたパスクエリについてRMQで答えが求まる。
最後に各クエリについて、分解した2つのパスの答えから小さい方を取って答える。
だいぶ日本語がアレになったけど許して
239: 2023/12/22(金)02:03 AAS
HL分解とやらが未知の時代に出題したかったぜ
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)という感じか
上下前次1-新書関写板覧索設栞歴
あと 721 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.117s