[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
181(1): 2023/12/21(木)23:54 AAS
おれ青の真ん中ぐらいだけどラグランジュ補間しらん
182: 2023/12/21(木)23:56 AAS
ネトストer、ここから追放されてXの奴らの質問箱でも荒らし回ってたガチのバケモンだから普通にそのうち開示はされそう(余罪はありそうだし)
183: 2023/12/21(木)23:56 AAS
入門はやっぱり赤マスのブログがいいかな
めちゃくちゃわかりやすいし、具体例も豊富
あとは、ABC-ExのNyaan解説読み漁るだけでもレベルの高い知識も補充できる
AGC-Dは自力AC目指してまだ解説見てないからどの程度かわからんけど
184: 2023/12/21(木)23:58 AAS
>>181
青真ん中なら知っといていい
それ自体はそんなに難しくない話だし、水でも理解できると思う
185: 2023/12/21(木)23:58 AAS
いやもうくんerは開示されて服役中だよ
186: 2023/12/21(木)23:59 AAS
難しくないといったけど、ググって出てくる解説が見た目そんなにわかりやすくないな
187: 2023/12/22(金)00:01 AAS
ager=くんer=初動er=芝浦er=受験数学er
188: 2023/12/22(金)00:02 AAS
まとまった資料というと、Nyaan Libraryを見ればFPSで高速でできるものが大体網羅されている
189: 2023/12/22(金)00:10 AAS
FPSと数え上げとの対応 の初めて向けは赤マスさんのが良くて、
FPSと数列との対応 の初めて向けはtatyamさんのが良いと思う
tatyamさんの方の記事見れば ABC321-F とか解けると思う
高度なアルゴリズムはnyaanさんの解説とか赤マスさんの「高速に計算できるものたち」記事とかで
190: 2023/12/22(金)00:15 AAS
赤マスって呼び方定着してるけど色変したらややこしいだろ変数の命名下手かよ
緑マスもしかり
191: 2023/12/22(金)00:16 AAS
赤マスの方はそうそう変わらんでしょ
192: 2023/12/22(金)00:19 AAS
>>179です
教えてくれた人たちありがとう、とりあえず赤マスさんの読み終わったら教えてくれたやつ色々読み漁ってみます
193: 2023/12/22(金)00:19 AAS
マスプヨとマベマスでいいだろ
194: 2023/12/22(金)00:19 AAS
クリスマス暇だしヒュ手出してみるか
で、何から学べばいい？
195: 2023/12/22(金)00:20 AAS
呼びづらいし、マップーとママでええか？
196: 2023/12/22(金)00:23 AAS
赤コーダーには様をつけろよ
197: 2023/12/22(金)00:23 AAS
サマス
198: 2023/12/22(金)00:24 AAS
最早Xの寒色の奴らよりは真面目だなこのスレ民
199(1): 2023/12/22(金)00:25 AAS
授業でやったけどラグランジュ補間って問題になるの？
点列補間してグラフ書くだけのやつかと思ってたが
200: 2023/12/22(金)00:28 AAS
ABC208Fとか
これはラグランジュ補間やるだけじゃなくて比較的面白いと思う
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～😎
上下前次1-新書関写板覧索設栞歴
あと 741 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.017s