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

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

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

760(1): 2024/06/18(火)18:19 AAS
最大長方形と認識してなかったが、ソート順に並べてLCPテーブルをもとにガチャガチャやるのはド典型じゃね

761: 2024/06/18(火)18:24 AAS
>>760
なるほどーありがとう
Twitterでワード検索かけてもこれについて解法ツイートしてる人が2人しかいなくて、なんだこれはになってた

762: 2024/06/18(火)18:28 AAS
最大長方形パートは別として、LCP table使うのは大体suffix arrayとセットでやることが多いテクなので、そういう問題解いてたらかなり思いつきやすいはず

763: 2024/06/18(火)18:32 AAS
なるほど
勉強になります

764: 2024/06/18(火)18:45 AAS
>>759
ひろゆきは2chを作ったからポテ橙だな

765: 2024/06/18(火)18:45 AAS
問題集まってんのはこのページのSuffixArray,LCPあたりとか？
https://blog.hamayanhamayan.com/entry/2017/03/25/005452
どちらかというとセグ木と組み合わせることが多いな

766(1): 2024/06/18(火)18:53 AAS
LCPテーブルにセグ木って何乗せるの

767: 2024/06/18(火)18:53 AAS
わざわざありがとう
セグ木と組み合わせることもあるんだね

768: 2024/06/18(火)18:55 AAS
LCPのrangeminqueryにセグ木使うのはライブラリ盆栽足りてないと思うので

769: 2024/06/18(火)19:01 AAS
二分探索十分速いし、構築も速いからセグ木でいいかなと思ってたけど、もっといい方法がある？

770: 2024/06/18(火)19:04 AAS
>>766
んさmin

771: 2024/06/18(火)19:06 AAS
構築O(N)クエリO(1)の静的RMQ

772: 2024/06/18(火)19:06 AAS
確かに二分探索前提ならセグ木のほうが定数倍早そうだ
インコ晒したので吊りますありがとう

773: 2024/06/18(火)19:09 AAS
いや、他の高速なRMQど忘れしてたから復習の機会になった
セグ木じゃない方がいい場合も割とありそう

775: 2024/06/18(火)19:11 AAS
マータ赤マスが競プロに貢献してる

776: 2024/06/18(火)19:12 AAS
LCPでセグ木内二分探索するわけないやん俺やっぱりインコだわ
常にstaticRmQでいいしもう一回吊りますありがとう

777: 2024/06/18(火)19:13 AAS
え、LCPで二分探索する問題あったと思うけど

778: 2024/06/18(火)19:16 AAS
272Fにあったので更に吊りますありがとう

779: 2024/06/18(火)19:17 AAS
吊りスギィ！