[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
166: 2023/12/21(木)23:40 AAS
ラグランジュ補完先輩
167(1): 2023/12/21(木)23:40 AAS
>>158
お前暴言連投してるから開示候補な
168: 2023/12/21(木)23:42 AAS
>>167
特定人物に対してネトストしてここに悪口書きまくってる自らを棚に上げて匿名相手への暴言が開示対象だと思ってるなら勝手にどうぞ
169: 2023/12/21(木)23:43 AAS
とりあえずここはもうお前の居場所じゃないからとっとと去れよ
170: 2023/12/21(木)23:44 AAS
Lagrange補完もPolynomial Taylor Shiftも十分賢いから、そこで頑張っても定数倍の改善しかなさそう
171: 2023/12/21(木)23:44 AAS
もうネトストerは無視してデ・アの話とか競プロの話してればいいよ
どうせ競プロ殆どやってないようなやつだからそのうち消える
172: 2023/12/21(木)23:45 AAS
ラグランジュ補完やるだけみたいな問題って確か試験管橙diffとかにあったと思うけど、今ABCとかで出たらどれくらいになるかな
173: 2023/12/21(木)23:46 AAS
くんerが消えた理由ってやっぱ開示されて逮捕されたからでしょ
仲間たちと同じように刑務所で心を入れ替えて精進して、せめて黄タッチ（できれば黄溜まりより上）になったらおしゃべりしよう
174: 2023/12/21(木)23:46 AAS
うざいのはみんなそうだと思うけど親でも殺されたかのようにキレ散らかしてるのはunkの身内か何かか？unkの評判にも繋がりかねないから程々にね
175: 2023/12/21(木)23:48 AAS
くんにブロックされてるんだけどスレ民ってバレたのか？でも俺ネトストしたことないぞ
176: 2023/12/21(木)23:49 AAS
2020年以前は高度な知識を仕入れているのは専ら暖色以上という感じだったから、ラグランジュ補間やるだけでも結構diffが高いけど、今だと下手したら青下位でも検索して貼ってくるんじゃないかな
177: 2023/12/21(木)23:51 AAS
出る位置にもよる
Gで出たらそもそも青下位erは解けないと決めつけて諦めるのが多いので、思ったより解かれないかも
Fだと結構解かれそう
178: 2023/12/21(木)23:53 AAS
ラグランジュ補完ってまあ確かに検索で辿り着きやすそうな操作だし授業とかでも割とやるからそんなもんか
179(1): 2023/12/21(木)23:53 AAS
FPSやりたいんだがとりあえずマスさんのブログ読めばいい？他にもおすすめの資料あったら教えてほしい(最終的にはこの間のAGC-Dの解説が理解できるくらいの知識を身につけたい)
180: 2023/12/21(木)23:53 AAS
最近は水緑でもラグランジュ補完知ってたりするしそれこそunkくらいのレベルでもやるだけなら通しそう
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)) くらいで
上下前次1-新書関写板覧索設栞歴
あと 756 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.016s