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

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

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

622: 09/09(火)21:06 AAS
ダークトライアドは反省しません

623: 09/09(火)22:05 AAS
toridaiou

625: 09/09(火)23:28 AAS
どうでもいいけど値の範囲が有限ならピボットを有限範囲の中間にし続けることでクイックソートの計算量がNの2乗より小さくなるな

626: 09/09(火)23:29 AAS
最悪計算量が

627: 09/10(水)00:09 AAS
すまんクイックセレクトで分割すりゃよくね

628: 09/10(水)00:11 AAS
つか値の範囲が有限なら計算量にminmaxがかかるやろ
N支配的で見るのやめろ

629: 09/10(水)00:38 AAS
クイックセレクトの最悪はn^2じゃん
ちょっと変えるだけで決定的になるのが面白いねという話

630: 09/10(水)00:51 AAS
median of medians使えよ

631: 09/10(水)00:54 AAS
お前の手口でもnlogminmaxとかにはなるんじゃね

632: 09/10(水)00:57 AAS
上のビットから見るな
下のビットから見なさい

633: 09/10(水)00:59 AAS
radixsortやんけ

634: 09/10(水)01:01 AAS
binarytrieを動的に作りゃnlognか
すまんガイジ難しくね

635: 09/10(水)01:19 AAS
上位ビットに憧れるのをやめればいい(long longではなくintを使いなさいの意)

636: 09/10(水)02:29 AAS
天野くんのはすっごい硬い

637: 09/10(水)10:47 AAS
つかO(n)ソートならsuffixarrayにでも乗せりゃよくね
10^11451419198103934545364364を間に挟んでsaやるだけ

638: 09/10(水)10:48 AAS
1からNの整数集合を各部分合計が同じになるように2つ以上の部分集合に分割する方法はどのような場合存在する？
分割とは各部分集合の積が空で和が元の集合に一致すること

639: 09/10(水)10:50 AAS
割と自明な解が存在したわ
俺ガイジですありがとう
外部ﾘﾝｸ:x.com

640: 09/10(水)10:56 AAS
suffix arrayだと文字列長になるからO(nlogminmax)じゃね？と思ったけどintの比較や掛け算回路があるのでO(1)で終わるだけか
厳密な計算式が分かりません
みんなでえびちゃんに叱られよう

641: 09/10(水)11:08 AAS
無理やんけ
saisの初回にバケットソートしとるからO(n+w)やわ吊りますさようなら

642: 09/10(水)11:10 AAS
値を√w個の√w文字列に分割とかすりゃいけんじゃね知らんけど

643: 09/10(水)11:12 AAS
アルゴリズムの話はGPTとしてろよ

644: 09/10(水)11:13 AAS
しょーもな

645: 09/10(水)11:14 AAS
アルハラやめろ😡

646: 09/10(水)11:14 AAS
アルゴリズムか右手と戯れることしかできない人間

647: 09/10(水)11:17 AAS
デアスレ！？

648: 09/10(水)11:17 AAS
スレ間違えてないか？

649: 09/10(水)11:32 AAS
入力長ってそもそもnlogminmaxだし、比較や四則演算はlogminmaxかかるぞ
64bitだと定数長だからO(n)として扱っているだけで多倍長だと変わる

650: 09/10(水)11:36 AAS
そらそうやけど競範囲なら10^1145141919とか使わんでも1145143643641919810とか64bitinf使えばええし
2進数01列をsaに乗せてソートするとO(nlog)やが同じことは114514進数でもできるわけで

651: 09/10(水)11:40 AAS
wをよしなに選べばo(nlogminmax)になるやろけどめんどくせどうせクソ遅いやろ普通にソートしろ