[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
177: 2023/12/24(日)16:51 AAS
ダイクストラってヒープよりセグメントツリーのほうが早くね
弱点は実装のキモさだけ
178: 2023/12/24(日)16:55 AAS
俺の思ってるやり方と違うかもだけど ヒープの方が簡単じゃない？
179: 2023/12/24(日)16:56 AAS
あと、構築分と候補がくすない場合はヒープのほうが早そう
180: 2023/12/24(日)16:58 AAS
外部ﾘﾝｸ:x.com
181: 2023/12/24(日)16:59 AAS
寒色マンさんのクリスマスおまんこにみょ〜ん
182: 2023/12/24(日)17:06 AAS
ヒープのほうが簡単なのはそれはそう
セグ木だと2つのinfを持つことになるからクソキモい実装になる
頂点数NのダイクストラをN頂点の点更新セグ木に乗せる
初期化は全ノードinf-1、スタート地点の頂点を距離0
頂点を取り出す時はセグ木の二分探索の気持ちで最小要素を探せばよくO(logN)
最短距離が確定したら別配列に答えを格納してから自身をinfで更新
辺の伝播はinf未満の頂点に対して行えばよく、現在値の取得はO(1)で更新するならO(logN)
省1
183: 2023/12/24(日)17:11 AAS
セグ木でやるやり方はわかったけどこれで普通のヒープより速いの？
かなり非自明だ
184(1): 2023/12/24(日)17:18 AAS
探索候補から除けるためにinfにするの、確かに言いようのないキモさを感じるな
本来十分小さいから除外するものなのに、実装としては一番大きい値を代入するところが
185: 2023/12/24(日)17:20 AAS
俺のセグ木が遅いだけなのか？
もうちょい頑張るとO(V+ElogV)に落とせそう
186: 2023/12/24(日)17:22 AAS
ヒープのダイクストラもElogVでは？
オーバーヘッドはヒープのほうが小さそうに感じるけど
187: 2023/12/24(日)17:24 AAS
>>184
if d(v)≠inf: d(v) ← d(u) + dist(u,v)
で、O(1)とはいえ大小判定前に不一致判定を挟むのもキモい
188(1): 2023/12/24(日)17:28 AAS
知らんけどセグ木って要素数簡単に変えられるの？
189: 2023/12/24(日)17:29 AAS
>>188
不可能
けれどもダイクストラって事前に頂点数が明らかだから、距離ではなく頂点をノードに載せて、距離を値とすればよくないか
190: 2023/12/24(日)17:31 AAS
誰か試してくれ
俺がやるとセグ木のほうが2割速い
191: 2023/12/24(日)17:32 AAS
じゃあヒープの方が速いケースが多いと思うが
192: 2023/12/24(日)17:38 AAS
よく考えたらレベルの低い不能な議論だったわ
193: 2023/12/24(日)17:45 AAS
Newbie tourist
194: 2023/12/24(日)17:49 AAS
微博は取り締まらないガバマン運営
195: 2023/12/24(日)17:50 AAS
Xmasコンやるか
196: 2023/12/24(日)18:03 AAS
チーム組むぞ
197: 2023/12/24(日)18:10 AAS
微博無法地帯なの？
198: 2023/12/24(日)18:23 AAS
ネットワークフローアルゴリズムの新刊良さそうだな
199: 2023/12/24(日)18:41 AAS
クリスマスコンなんで健常者は参加できない時間帯にやるんだ泣
俺悔しいよ
200: 2023/12/24(日)18:51 AAS
聖夜だしビジュアライザ無限ポチポチで過ごすか
201: 2023/12/24(日)19:06 AAS
クリスマスだからか書き込み少ないな
202: 2023/12/24(日)19:12 AAS
ヒトカラ行こうとしたら料金クッソ高くて泣いちゃった🥺
クリコン1人で出るか
203: 2023/12/24(日)19:21 AAS
どうやってもセグ木ダイクストラはO((V+E)logV)から落ちませんでした
いかがでしたか？
204: 2023/12/24(日)19:39 AAS
例年1問くらいは解けるもんだが、今年無理説あるな
205: 2023/12/24(日)19:45 AAS
結局みんなFAKE野郎というわけか
深夜のこどふぉくらいにはラブホから参加しとけよ、性交を中断してでも
206: 2023/12/24(日)19:45 AAS
俺らはAC射精完了出来れば良いと誓った仲じゃないか
207: 2023/12/24(日)20:35 AAS
ぬこぬこ...
208: 2023/12/24(日)21:00 AAS
🧅をあんまり刺激しないほうがいいと思う
209: 2023/12/24(日)21:02 AAS
クリトリス？
210: 2023/12/24(日)21:08 AAS
はい
211: 2023/12/24(日)21:15 AAS
はいじゃないが
212: 2023/12/24(日)21:38 AAS
？
213: 2023/12/24(日)21:56 AAS
みんな書き込んでない
どうせセックスしてんだろ
214: 2023/12/24(日)21:58 AAS
FAKEがよおおおおおおおおおおおお！！！！！！！
215: 2023/12/24(日)21:59 AAS
がよおerも怒ってます
216: 2023/12/24(日)22:01 AAS
それはそう
セックスとか童貞とか謎煽りしてるやつ定着してたけど皆呼吸と同じくらい自然にやってるから効くもクソもない
217: 2023/12/24(日)22:05 AAS
今日くらいは彼女とセックスするだろ
案の定agerすら書き込んでないな
218: 2023/12/24(日)22:06 AAS
低学歴も高学歴も彼女くらいはいるからな
219: 2023/12/24(日)22:09 AAS
知能が低くともメスインコとは付き合えるというわけか
220: 2023/12/24(日)22:13 AAS
たまねぎまだ続けてる？
221: 2023/12/24(日)22:13 AAS
ガイジスレ民の場合逮捕されて書き込めない人も多いからFAKE扱いは早いんじゃないか
222: 2023/12/24(日)22:20 AAS
誰か自閉症の治療法を見つけてほしい
223: 2023/12/24(日)22:32 AAS
昨日のB問題、PythonとC＋＋であまりに難易度が違いすぎる上に、C＋＋だと緑くらいの実力だと初見でACするのほぼ無理なレベルじゃねこれ
公式解説のやり方にしてもsnukeさんのやり方にしてもあまりに再現性が無さすぎる
224: 2023/12/24(日)22:35 AAS
全体を移動させて>0のみを考えるって割と基本的だと思うけど
225: 2023/12/24(日)22:35 AAS
CやEに関しては自分の実力不足だと割り切れなくもないが、Bに関しては完全に運営の調整不足だろ
226(1): 2023/12/24(日)22:37 AAS
pythonだと
print(r//m - (l-1)//m)
これで終わりだからな
227: 2023/12/24(日)22:40 AAS
インコだとそう感じちゃうよね
実際はただの算数だから言語による差は微小
228: 2023/12/24(日)22:42 AAS
>>226
これが導ければpythonだろうがcだろうが関係なくね？
229: 2023/12/24(日)22:42 AAS
C＋＋だと誤差が絡んできてpythonほど簡潔には実装できないんだよ
230: 2023/12/24(日)22:43 AAS
modの仕様を誤差って言うのか？
231: 2023/12/24(日)22:43 AAS
フェル小もわからないのに自称数学ができる人()
232: 2023/12/24(日)22:45 AAS
どの言語使うかは自由なのに何が調整不足だよお前が調整しろ
そもそも言語差あるのは前提なんだから一々運営叩くなよインコ
233: 2023/12/24(日)22:48 AAS
戦犯はC++の負の除算を切り捨てにしなかった言語仕様にあるだろ
234: 2023/12/24(日)22:49 AAS
失敗の原因を自分以外に押し付けたがるのはインコ典型
235: 2023/12/24(日)22:52 AAS
C++だと大変だった！とか騒いでるインコ、Python使ってTLEしてピーピー鳴いてるインコと一緒でマジでしょうもない
そんなにPythonのが楽ならPython使えばいいだけだし、C++でも配点的には適正なぐらい簡単だろ
236: 2023/12/24(日)22:55 AAS
普段c++で得もしてる癖に損したときだけ騒ぎやがる
自分の実力不足を認めない限りお前はそこで停滞するぞインコ
237: 2023/12/24(日)22:57 AAS
python勢のインコという疑似撞着語法
238: 2023/12/24(日)22:57 AAS
pythonってmultisetがないんだっけ よーしらん
239: 2023/12/24(日)22:58 AAS
インコは人間の悪い部分も真似てるな
240: 2023/12/24(日)23:01 AAS
平衡二分探索木が標準でないネタは昔から言われまくってるけど、普通に解決してる
241: 2023/12/24(日)23:04 AAS
検索してコピってくるだけやからな
242: 2023/12/24(日)23:07 AAS
緑ってBのC++実装に初見で対応できないってマジ？
それでUnionFindとかセグ木は知っているんだから知識のバランス歪すぎだろ
243: 2023/12/24(日)23:08 AAS
全員信用できない
244: 2023/12/24(日)23:09 AAS
いや、さすがにこの時間にC++のせいでBが解けないだのどうこうでレスバしてるやつは保証書付き童貞だろ
245: 2023/12/24(日)23:10 AAS
値が±1とかズレてペナ出しまくったとかならまだ分かるけど、コンテスト中に通し切れないのはよく分からん
246: 2023/12/24(日)23:13 AAS
インコの愚痴はスルーしましょう
247: 2023/12/24(日)23:13 AAS
初見ACの意味がノーペナACならまあ理解できるな
流石にコンテスト中には通せるだろうけど、数ペナ出す程度には緑はおバカなレベル帯という印象
248: 2023/12/24(日)23:16 AAS
Bは分散がかなり大きい問題だよね
灰でも苦戦せずに通せるやつがいる一方で、水色でも時間内に通せない人もいる
249: 2023/12/24(日)23:16 AAS
男は黙ってメスインコクリスマスfuck
じゃなかったbrainfuckだよな〜
250: 2023/12/24(日)23:16 AAS
> 「この人達は、本当は数学なんかできないな」
と思った人達をブロックしただけだ。
緑マスくん可哀想...
251: 2023/12/24(日)23:17 AAS
脳姦
252: 2023/12/24(日)23:19 AAS
クリスマスコンと🧅にボロボロにされてたんだな
253: 2023/12/24(日)23:20 AAS
クリスマスコンも
254: 2023/12/24(日)23:21 AAS
順位表見た感じ青のratedでもB通せてない人いるな
255: 2023/12/24(日)23:22 AAS
青で除算でやるやり方思いつかないわけないし、ガチでプログラミングできないんだな
256: 2023/12/24(日)23:22 AAS
普通にペナって飛ばしてその後通す価値無いと判断して捨てただけだろ
緑が解けないのとは訳が違う
257: 2023/12/24(日)23:23 AAS
俺も初めてfloor-ceilしたとき脳バグったからなー
上下前次1-新書関写板覧索設栞歴
あと 745 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.359s