[過去ログ]
競技プログラミングにハマるプログラマのスレ 143 (1002レス)
競技プログラミングにハマるプログラマのスレ 143 http://medaka.5ch.net/test/read.cgi/prog/1703141733/
上
下
前
次
1-
新
通常表示
512バイト分割
レス栞
このスレッドは過去ログ倉庫に格納されています。
次スレ検索
歴削→次スレ
栞削→次スレ
過去ログメニュー
182: 仕様書無しさん [sage] 2023/12/21(木) 23:56:43.93 ネトストer、ここから追放されてXの奴らの質問箱でも荒らし回ってたガチのバケモンだから普通にそのうち開示はされそう(余罪はありそうだし) http://medaka.5ch.net/test/read.cgi/prog/1703141733/182
183: 仕様書無しさん [sage] 2023/12/21(木) 23:56:45.67 入門はやっぱり赤マスのブログがいいかな めちゃくちゃわかりやすいし、具体例も豊富 あとは、ABC-ExのNyaan解説読み漁るだけでもレベルの高い知識も補充できる AGC-Dは自力AC目指してまだ解説見てないからどの程度かわからんけど http://medaka.5ch.net/test/read.cgi/prog/1703141733/183
184: 仕様書無しさん [sage] 2023/12/21(木) 23:58:04.31 >>181 青真ん中なら知っといていい それ自体はそんなに難しくない話だし、水でも理解できると思う http://medaka.5ch.net/test/read.cgi/prog/1703141733/184
185: 仕様書無しさん [sage] 2023/12/21(木) 23:58:30.49 いやもうくんerは開示されて服役中だよ http://medaka.5ch.net/test/read.cgi/prog/1703141733/185
186: 仕様書無しさん [sage] 2023/12/21(木) 23:59:29.35 難しくないといったけど、ググって出てくる解説が見た目そんなにわかりやすくないな http://medaka.5ch.net/test/read.cgi/prog/1703141733/186
187: 仕様書無しさん [sage] 2023/12/22(金) 00:01:53.27 ager=くんer=初動er=芝浦er=受験数学er http://medaka.5ch.net/test/read.cgi/prog/1703141733/187
188: 仕様書無しさん [sage] 2023/12/22(金) 00:02:28.62 まとまった資料というと、Nyaan Libraryを見ればFPSで高速でできるものが大体網羅されている http://medaka.5ch.net/test/read.cgi/prog/1703141733/188
189: 仕様書無しさん [sage] 2023/12/22(金) 00:10:59.49 FPSと数え上げとの対応 の初めて向けは赤マスさんのが良くて、 FPSと数列との対応 の初めて向けはtatyamさんのが良いと思う tatyamさんの方の記事見れば ABC321-F とか解けると思う 高度なアルゴリズムはnyaanさんの解説とか赤マスさんの「高速に計算できるものたち」記事とかで http://medaka.5ch.net/test/read.cgi/prog/1703141733/189
190: 仕様書無しさん [sage] 2023/12/22(金) 00:15:34.79 赤マスって呼び方定着してるけど色変したらややこしいだろ変数の命名下手かよ 緑マスもしかり http://medaka.5ch.net/test/read.cgi/prog/1703141733/190
191: 仕様書無しさん [sage] 2023/12/22(金) 00:16:47.36 赤マスの方はそうそう変わらんでしょ http://medaka.5ch.net/test/read.cgi/prog/1703141733/191
192: 仕様書無しさん [sage] 2023/12/22(金) 00:19:05.49 >>179です 教えてくれた人たちありがとう、とりあえず赤マスさんの読み終わったら教えてくれたやつ色々読み漁ってみます http://medaka.5ch.net/test/read.cgi/prog/1703141733/192
193: 仕様書無しさん [sage] 2023/12/22(金) 00:19:06.51 マスプヨとマベマスでいいだろ http://medaka.5ch.net/test/read.cgi/prog/1703141733/193
194: 仕様書無しさん [sage] 2023/12/22(金) 00:19:36.44 クリスマス暇だしヒュ手出してみるか で、何から学べばいい? http://medaka.5ch.net/test/read.cgi/prog/1703141733/194
195: 仕様書無しさん [sage] 2023/12/22(金) 00:20:47.04 呼びづらいし、マップーとママでええか? http://medaka.5ch.net/test/read.cgi/prog/1703141733/195
196: 仕様書無しさん [sage] 2023/12/22(金) 00:23:25.09 赤コーダーには様をつけろよ http://medaka.5ch.net/test/read.cgi/prog/1703141733/196
197: 仕様書無しさん [sage] 2023/12/22(金) 00:23:48.76 サマス http://medaka.5ch.net/test/read.cgi/prog/1703141733/197
198: 仕様書無しさん [sage] 2023/12/22(金) 00:24:02.19 最早Xの寒色の奴らよりは真面目だなこのスレ民 http://medaka.5ch.net/test/read.cgi/prog/1703141733/198
199: 仕様書無しさん [sage] 2023/12/22(金) 00:25:10.93 授業でやったけどラグランジュ補間って問題になるの? 点列補間してグラフ書くだけのやつかと思ってたが http://medaka.5ch.net/test/read.cgi/prog/1703141733/199
200: 仕様書無しさん [sage] 2023/12/22(金) 00:28:21.95 ABC208Fとか これはラグランジュ補間やるだけじゃなくて比較的面白いと思う http://medaka.5ch.net/test/read.cgi/prog/1703141733/200
201: 仕様書無しさん [sage] 2023/12/22(金) 00:31:15.61 >>199 ど直球のラグランジュ補完やるだけの問題だからネタバレしちゃうけど、これとか(上で言ってた試験管橙diff) https://atcoder.jp/contests/arc033/tasks/arc033_4 http://medaka.5ch.net/test/read.cgi/prog/1703141733/201
202: 仕様書無しさん [sage] 2023/12/22(金) 00:33:48.53 多項式じゃないだけでオーバーシュートして使い物にならない補完くん http://medaka.5ch.net/test/read.cgi/prog/1703141733/202
203: 仕様書無しさん [sage] 2023/12/22(金) 00:33:52.12 ABCWriterもよくやってるNyaanさんはFPSかなり好きだから、FPSがより普及したらこの程度のやるだけ問題はそのうちABC-Fで出てもおかしくなさそう(前提知識がなくても解けるとは思うし) http://medaka.5ch.net/test/read.cgi/prog/1703141733/203
204: 仕様書無しさん [sage] 2023/12/22(金) 00:35:06.59 マスさんの実績を調べてたらマスさんアンチ湧いててくっそわろた アンチの内容も難癖つけるだけで更にわろたわ 嫉妬してるんだろうな http://medaka.5ch.net/test/read.cgi/prog/1703141733/204
205: 仕様書無しさん [sage] 2023/12/22(金) 00:35:10.94 ヒュ精進、わからんよな(AHCで1から強くなった人間がまだほとんどいないため) http://medaka.5ch.net/test/read.cgi/prog/1703141733/205
206: 仕様書無しさん [sage] 2023/12/22(金) 00:36:09.95 行列木定理が好きなwriterいたよな http://medaka.5ch.net/test/read.cgi/prog/1703141733/206
207: 仕様書無しさん [sage] 2023/12/22(金) 00:36:51.81 マスさんレベルの天才紹介なら歓迎するのにね http://medaka.5ch.net/test/read.cgi/prog/1703141733/207
208: 仕様書無しさん [sage] 2023/12/22(金) 00:38:47.48 ratism精神を全面に押し出す(インコ人間境界線など)ことでスレ全体のレートを上げようとするのも良かったけど、この真面目にデ・アの話をする方向性でスレが安定したら本格的ににスレ民の平均レートが高くなりそう http://medaka.5ch.net/test/read.cgi/prog/1703141733/208
209: 仕様書無しさん [sage] 2023/12/22(金) 00:39:12.64 インコ総活躍社会を目指して、世界の天才競プロer紹介みたいな職でagerを再雇用してもいいけど、本人がやる気ないからどうしようもない http://medaka.5ch.net/test/read.cgi/prog/1703141733/209
210: 仕様書無しさん [sage] 2023/12/22(金) 00:39:21.65 行列木定理は初めて知った時感動した 最初に発明したやつ凄すぎる http://medaka.5ch.net/test/read.cgi/prog/1703141733/210
211: 仕様書無しさん [sage] 2023/12/22(金) 00:42:04.74 へへ...照れるやい! http://medaka.5ch.net/test/read.cgi/prog/1703141733/211
212: 仕様書無しさん [sage] 2023/12/22(金) 00:42:34.30 >>202 逆に次数が小さく抑えられるような多項式を相手にすると汎用的でかなり強い http://medaka.5ch.net/test/read.cgi/prog/1703141733/212
213: 仕様書無しさん [sage] 2023/12/22(金) 00:43:12.86 過去スレ精進がスレレートを上げる以外にも有効になる日も近い http://medaka.5ch.net/test/read.cgi/prog/1703141733/213
214: 仕様書無しさん [sage] 2023/12/22(金) 00:43:32.19 そのうち競プロの解説リンクにガイジスレが貼られるかも http://medaka.5ch.net/test/read.cgi/prog/1703141733/214
215: 仕様書無しさん [sage] 2023/12/22(金) 00:44:53.22 元からAtCoder非公式最有力フォーラムなのではい http://medaka.5ch.net/test/read.cgi/prog/1703141733/215
216: 仕様書無しさん [sage] 2023/12/22(金) 00:45:30.43 昔は貼られてたのによお http://medaka.5ch.net/test/read.cgi/prog/1703141733/216
217: 仕様書無しさん [sage] 2023/12/22(金) 00:46:25.75 nimさんだけじゃなくて社長も宣伝してくれよな http://medaka.5ch.net/test/read.cgi/prog/1703141733/217
218: 仕様書無しさん [sage] 2023/12/22(金) 00:46:37.60 お前らデ・アの話しろよ、みたいなレスよくあるけどそういうレスしなくても何でもいいから話題さえ提供すれば勝手にそういう流れになりそう http://medaka.5ch.net/test/read.cgi/prog/1703141733/218
219: 仕様書無しさん [] 2023/12/22(金) 00:47:27.16 UTの赤コーダーが1年生くらいのときに「競技プログラミングと線形代数」みたいなのを(texとかではなくコピー用紙に)書いたpdfで行列木定理とかその他諸々が紹介されてたよな http://medaka.5ch.net/test/read.cgi/prog/1703141733/219
220: 仕様書無しさん [sage] 2023/12/22(金) 00:48:46.50 >>218 それな 本当に競プロをやってる(真の意味でのやってる)ならば、こういう話応えのある話題が提供されれば反応するはずだからな http://medaka.5ch.net/test/read.cgi/prog/1703141733/220
221: 仕様書無しさん [sage] 2023/12/22(金) 00:49:44.35 安定のでぐわ http://medaka.5ch.net/test/read.cgi/prog/1703141733/221
222: 仕様書無しさん [] 2023/12/22(金) 01:09:48.19 問題作ったけど多分出せるとこないから誰か解いて 各頂点に整数A_iが書かれたN頂点の木に対して、以下の形式のクエリがQ個与えられるのでそれぞれ答えよ。 ・頂点u, vを結ぶパス上の頂点iに対して、A_iの最小値を求めよ。 【入力】N, Q, A_i, 辺の情報, 各クエリの2頂点 【制約】N, Q ≦ 10^5, A_i ≦ 10^9 HL分解はオーバーキル&俺が知らないからNG http://medaka.5ch.net/test/read.cgi/prog/1703141733/222
223: 仕様書無しさん [sage] 2023/12/22(金) 01:15:00.70 >>222 HL分解を知らないならオイラーツアーをやればいいじゃない(DFS順に頂点を並べるだけ) オイラーツアーを最小値取得セグ木に載せてAC射精完了 やるだけだしABC-Fで水〜青くらいかな http://medaka.5ch.net/test/read.cgi/prog/1703141733/223
224: 仕様書無しさん [sage] 2023/12/22(金) 01:16:28.22 オフラインなら各クエリのLCAを前計算 minセグ木を一個持ってdfs http://medaka.5ch.net/test/read.cgi/prog/1703141733/224
225: 仕様書無しさん [] 2023/12/22(金) 01:22:45.81 >>223 >>224 概ね伝わったから正解 こういうシンプルな問題を考えるのが好きなんだけど無限に既出で泣ける ちな水インコ http://medaka.5ch.net/test/read.cgi/prog/1703141733/225
226: 仕様書無しさん [sage] 2023/12/22(金) 01:25:59.84 オイラーツアーでパスクエリって処理できたっけ http://medaka.5ch.net/test/read.cgi/prog/1703141733/226
227: 仕様書無しさん [sage] 2023/12/22(金) 01:29:44.18 >>226 マス様がオイラーツアーの記事書いてくれてたはず http://medaka.5ch.net/test/read.cgi/prog/1703141733/227
228: 仕様書無しさん [sage] 2023/12/22(金) 01:33:14.07 もしかして>>223と>>224は違う解法なのか 一応ちゃんと想定通りに伝わったのは>>224のほう http://medaka.5ch.net/test/read.cgi/prog/1703141733/228
229: 仕様書無しさん [sage] 2023/12/22(金) 01:33:53.37 普通のやり方だと群じゃないとダメじゃね? http://medaka.5ch.net/test/read.cgi/prog/1703141733/229
230: 仕様書無しさん [sage] 2023/12/22(金) 01:39:29.67 >>228 すまん、パスクエリをHL分解じゃなくてオイラーツアーで処理したことがあまりなかったから適当に答えてしまった(1ペナ) 部分木クエリと混同してたけど、最小値はそのままやるだけだと逆元がないからダメっぽいから224みたいにオフラインにして探索順を工夫してまとめてやるしかなさそう https://maspypy.com/euler-tour-のお勉強 http://medaka.5ch.net/test/read.cgi/prog/1703141733/230
231: 仕様書無しさん [sage] 2023/12/22(金) 01:42:03.26 LCAが素直かな クエリ先読みDFSでも解けないことはなさそうだけど、多分超激重実装になるし、どこかでLCAが必要になる気がする(ので本末転倒) http://medaka.5ch.net/test/read.cgi/prog/1703141733/231
232: 仕様書無しさん [sage] 2023/12/22(金) 01:46:48.22 オイラーツアーってDFS探索自体を指すような語感もなくはない(競プロ文脈ではテーブル作成まで包含することがほとんどだと思うが)から紛らわしいところがある http://medaka.5ch.net/test/read.cgi/prog/1703141733/232
233: 仕様書無しさん [sage] 2023/12/22(金) 01:47:51.32 最小共通祖先が既に分かっているなら、頂点u,vへのパス上のminAiを逐次計算すればO(N+Q) でもLCA求めたついでにクエリをダブリング処理するO((N+Q)logN)で絶対によいため LCAってO(N+Q)で求める方法あるっけ? http://medaka.5ch.net/test/read.cgi/prog/1703141733/233
234: 仕様書無しさん [sage] 2023/12/22(金) 01:56:11.18 少し考えたらありそうだけど、重実装なのは変わらんな 1回目のDFSは頂点ごとにクエリを持ち帰って、同じクエリが合流した頂点をLCAとすればO(N+Q)でLCAが求まる 2回目のDFSはLCA→u, LCA→vのminAiを求めればよく、1回目のDFSが書ける人なら当然これも書ける 最後にLCA→u,vの結果を合成して出力すれば合計でO(N+Q) http://medaka.5ch.net/test/read.cgi/prog/1703141733/234
235: 仕様書無しさん [sage] 2023/12/22(金) 01:58:40.35 minに逆元がないので嘘だわこれ 2回目のDFSがO(NQ)になるな http://medaka.5ch.net/test/read.cgi/prog/1703141733/235
236: 仕様書無しさん [sage] 2023/12/22(金) 02:00:16.91 モノイドがよぉ http://medaka.5ch.net/test/read.cgi/prog/1703141733/236
237: 仕様書無しさん [sage] 2023/12/22(金) 02:01:07.72 HL分解でいい感じにクエリ辺りの計算回数をlog回に落とすのが定番だけど、こういう解法を考えるのに意味はありそうではある http://medaka.5ch.net/test/read.cgi/prog/1703141733/237
238: 仕様書無しさん [sage] 2023/12/22(金) 02:01:41.74 一応ちゃんと想定を書く 各クエリをLCAで2つのパスに分解して、子孫のほうに情報を持たせておく。 そしてminセグ木を一つ持って、dfs順に頂点iを走査しセグ木の要素をA_iに更新する(このときのセグ木のインデックスは頂点iの根からの距離)。すると、iの祖先が根から順番にセグ木に並んでいる状態になるので、iに持たせたパスクエリについてRMQで答えが求まる。 最後に各クエリについて、分解した2つのパスの答えから小さい方を取って答える。 だいぶ日本語がアレになったけど許して http://medaka.5ch.net/test/read.cgi/prog/1703141733/238
239: 仕様書無しさん [sage] 2023/12/22(金) 02:03:28.02 HL分解とやらが未知の時代に出題したかったぜ http://medaka.5ch.net/test/read.cgi/prog/1703141733/239
240: 仕様書無しさん [sage] 2023/12/22(金) 02:09:31.81 LCAライブラリをいじる手間を考えるとセグ木DFSのほうが実装楽そう クエリ対応のLCA持ってないし http://medaka.5ch.net/test/read.cgi/prog/1703141733/240
241: 仕様書無しさん [sage] 2023/12/22(金) 02:18:56.00 >>238 似たようなこと考えてたけど、セグ木じゃなくてmultisetでシミュするだけで良さそうだと思った http://medaka.5ch.net/test/read.cgi/prog/1703141733/241
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
メモ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 740 レスあります
スレ情報
赤レス抽出
画像レス抽出
歴の未読スレ
AAサムネイル
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.013s