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

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

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

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
まあ大体遅延セグ木じゃなくても解ける問題ではあるが

170: 2024/03/02(土)23:35 AAS
GPT4そこまで強くなったのか

171: 2024/03/02(土)23:36 AAS
GPT4が強いというより、今日のは全然頭使わないし典型という話

172: 2024/03/02(土)23:37 AAS
Eなんて考察1で遅延セグ木か、考察3でセグ木かしか無いでしょ
遅延が必須ってわけでもない

173: 2024/03/02(土)23:37 AAS
BITやセグ木の練習問題のつもりが遅延セグ木でブン殴られてるって話

174(1): 2024/03/02(土)23:38 AAS
セグ木やUFと比べてLCA出なさすぎじゃね？Gの初手とかではちょくちょく使うけど、F以下で使う問題最近全然見ない

175: 2024/03/02(土)23:38 AAS
セグ木は見た瞬間に思い付いたけど2番目の大きさと個数の乗せ方が分からんかった
twitterみても緑~水あたりでそういう人多そう

176: 2024/03/02(土)23:38 AAS
セグ木は見た瞬間に思い付いたけど2番目の大きさと個数の乗せ方が分からんかった
twitterみても緑~水あたりでそういう人多そう

177: 2024/03/02(土)23:38 AAS
G何でこれが600点扱いなのかわからん
F550とかでも良さそう