競技プログラミングにハマるプログラマのスレ 161

[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 161 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

135: 2024/03/02(土)23:12 AAS
ACLを使うならセグ木の勉強なんて一瞬で終わるし前提すぎる

136: 2024/03/02(土)23:13 AAS
マス君この前セグ木+DPの問題ACしてなかったか
セグ木履修済みなのでは

137: 2024/03/02(土)23:15 AAS
セグ木は知ってるけどF解けなかった
区間の総和と最小値と最大値求めるくらいしか出来ない…

138: 2024/03/02(土)23:16 AAS
>>134
Dここ最近で一番簡単だった
マジでそのままやるだけ

139(1): 2024/03/02(土)23:16 AAS
寒色インコ「やるだけ」

ｗ

140(1): 2024/03/02(土)23:17 AAS
2番目に大きい値とか誰かライブラリ作ってるやろ！→検索しても出てこない...

141: 2024/03/02(土)23:17 AAS
こどふぉないの

142: 2024/03/02(土)23:18 AAS
>>140
普通に順位クエリ対応したSetとかあるけど

143: 2024/03/02(土)23:18 AAS
あ、でもこの問題だと駄目だわ
すまん

144(1): 2024/03/02(土)23:19 AAS
>>139
ズレてるぞ

145: 2024/03/02(土)23:19 AAS
そもそも動的WMでそういう二次元領域に関するあれこれのクエリはだいたい解決できるので(今回はTLEしそうだが)

146(1): 2024/03/02(土)23:20 AAS
>>126
マス君ちゃんと方針書くようになったの偉い
Bでソートしてるの謎すぎるが

147: 2024/03/02(土)23:20 AAS
>>144
お前がな

148: 2024/03/02(土)23:21 AAS
最近苦しい

149: 2024/03/02(土)23:25 AAS
動的WM、log2個は遅すぎると話題

150: 2024/03/02(土)23:27 AAS
>>146
昇順だからソートしたんだけど、今思うとソートする必要なかったわ

151: 2024/03/02(土)23:28 AAS
Fdiff1300台は流石に違和感がある

152: 2024/03/02(土)23:28 AAS
パフォは大して変わってないのにちょっと順位いいなって思ったら
もしかしてベトナム勢出てませんか？

153: 2024/03/02(土)23:29 AAS
そりゃそうでしょ

154(1): 2024/03/02(土)23:30 AAS
つか動的WMって空間計算量が壊れんか？
WMは簡潔BBが使えるおかげで空間O(NlogN)bitだけど、動的は平衡二分木に乗せる関係で完備辞書の空間が爆発しそう

155: 2024/03/02(土)23:31 AAS
問題の見た目がセグ木すぎるし、載せるモノイドも典型的だし
diffは知識要素より考察量と実装量で決まるぞ

156: 2024/03/02(土)23:31 AAS
BBではなくBit Vectorでした

157: 2024/03/02(土)23:31 AAS
中国ではセグ木も初等データ構造扱いなんだろう

158: 2024/03/02(土)23:31 AAS
日本でもそうだろ

159(1): 2024/03/02(土)23:32 AAS
>>154
確かに座圧しても今回はダメそうだな

160: 2024/03/02(土)23:32 AAS
つーかローカルで6秒かかったからちょっと枝狩りしたんだけどあっとこのサーバーだと1秒くらいで終わってワロタ
定数倍気にしなくていいですか？

161: 2024/03/02(土)23:32 AAS
モノイド工夫して載せるみたいなのが一年前はこんなに解かれてなかったというお話

162: 2024/03/02(土)23:33 AAS
セグ木強化月間なので

163: 2024/03/02(土)23:33 AAS
コードテストで確認するといいぞ

164: 2024/03/02(土)23:33 AAS
大昔は遅延セグ木が今のLC木ぐらいのポジションだったのかもしれんが、今の遅延セグ木は大昔のUnionFindぐらいの扱いだろうな