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

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

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

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ぐらいの扱いだろうな

165: 2024/03/02(土)23:34 AAS
自分が貯金さえしていれば、いつどこへ動くかは、己のタイミングで決めてよくて、必ずしもぼろぼろになるまで頑張ってから辞める、またはずっと居続ける、ではなくてよいのね

166: 2024/03/02(土)23:34 AAS
ぶっちゃけセグ木で解くことがわかってればモノイドはGPT4に聞いても出てくる
普通に自力で解けるけど

167: 2024/03/02(土)23:34 AAS
>>159
つっても平衡二分木実装したことないから、空間計算量が本当に壊れるかわからん

168: 2024/03/02(土)23:34 AAS
遅延セグ木って昔はABC-G以降とかでしか見なかったのに7問制になってからEまで降りてきてるからな

169: 2024/03/02(土)23:35 AAS
まあ大体遅延セグ木じゃなくても解ける問題ではあるが