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

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

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

750: 仕様書無しさん [sage] 2024/06/18(火) 18:04:35.47 AAS
インコvsインコ

751: 仕様書無しさん [sage] 2024/06/18(火) 18:05:21.74 AAS
それ以前に年収と企業tierを同一視してる典型的インコだとバカにしてるんですよ

752: 仕様書無しさん [sage] 2024/06/18(火) 18:05:36.53 AAS
GAFAM以外はインコです

753: 仕様書無しさん [sage] 2024/06/18(火) 18:06:45.38 AAS
童貞は人口の再生産ができず滅びるのでTier F-です

754: 仕様書無しさん [sage] 2024/06/18(火) 18:06:51.94 AAS
アクセンチュアに嫉妬って発想が出てくるの確実にUT卒ではないよな

755: 仕様書無しさん [sage] 2024/06/18(火) 18:08:26.49 AAS
優秀かどうかは年収で決まります

756: 仕様書無しさん [sage] 2024/06/18(火) 18:08:44.88 AAS
河野agerの次はアクセンチュアagerか
インコは絶妙にしょうもないレベル帯をageるのが本当に好きだな

757: 仕様書無しさん [sage] 2024/06/18(火) 18:10:46.97 AAS
インコ向け就活サイトをバカにされて発狂インコ

758: 仕様書無しさん [sage] 2024/06/18(火) 18:11:37.37 AAS
ABC353Eのフレンズが紹介してる、ヒストグラムの最大長方形問題と同様の考え方でLCPを解くやつって典型？

759(1): 仕様書無しさん [sage] 2024/06/18(火) 18:12:46.90 AAS
ひろゆきもポテ黄だからスレ基準だとインコだけど優秀だしな

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

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

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

763: 仕様書無しさん [sage] 2024/06/18(火) 18:32:33.54 AAS
なるほど
勉強になります

764: 仕様書無しさん [sage] 2024/06/18(火) 18:45:48.13 AAS
>>759
ひろゆきは2chを作ったからポテ橙だな

765: 仕様書無しさん [sage] 2024/06/18(火) 18:45:50.21 AAS
問題集まってんのはこのページのSuffixArray,LCPあたりとか？
外部ﾘﾝｸ:blog.hamayanhamayan.com
どちらかというとセグ木と組み合わせることが多いな

766(1): 仕様書無しさん [sage] 2024/06/18(火) 18:53:37.23 AAS
LCPテーブルにセグ木って何乗せるの

767: 仕様書無しさん [sage] 2024/06/18(火) 18:53:59.03 AAS
わざわざありがとう
セグ木と組み合わせることもあるんだね

768: 仕様書無しさん [sage] 2024/06/18(火) 18:55:28.49 AAS
LCPのrangeminqueryにセグ木使うのはライブラリ盆栽足りてないと思うので

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

770: 仕様書無しさん [sage] 2024/06/18(火) 19:04:03.95 AAS
>>766
んさmin

771: 仕様書無しさん [sage] 2024/06/18(火) 19:06:02.82 AAS
構築O(N)クエリO(1)の静的RMQ

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

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

774: 仕様書無しさん [sage] 2024/06/18(火) 19:10:21.54 AAS
外部ﾘﾝｸ:maspypy.com
いつもの