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

**仕様書無しさん** · 2025/09/02(火) 00:01:54.45

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 240
https://medaka.5ch.net/test/read.cgi/prog/1751881831/
競技プログラミングにハマるプログラマのスレ 241
https://medaka.5ch.net/test/read.cgi/prog/1752227963/
競技プログラミングにハマるプログラマのスレ 242
https://medaka.5ch.net/test/read.cgi/prog/1752673864/
競技プログラミングにハマるプログラマのスレ 243
https://medaka.5ch.net/test/read.cgi/prog/1753012297/
競技プログラミングにハマるプログラマのスレ 244(旧)
https://medaka.5ch.net/test/read.cgi/prog/1753614298/
競技プログラミングにハマるプログラマのスレ 244(新)
https://medaka.5ch.net/test/read.cgi/prog/1753614302/
競技プログラミングにハマるプログラマのスレ 246
https://medaka.5ch.net/test/read.cgi/prog/1755125792/
競技プログラミングにハマるプログラマのスレ 247
https://medaka.5ch.net/test/read.cgi/prog/1755776229/
競技プログラミングにハマるプログラマのスレ 248
https://medaka.5ch.net/test/read.cgi/prog/1756116011/

**仕様書無しさん** · 2025/09/09(火) 22:59:54.26

https://karapaia.com/archives/52288285.html

**仕様書無しさん** · 2025/09/09(火) 23:28:46.96

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

**仕様書無しさん** · 2025/09/09(火) 23:29:04.40

最悪計算量が

**仕様書無しさん** · 2025/09/10(水) 00:09:25.44

すまんクイックセレクトで分割すりゃよくね

**仕様書無しさん** · 2025/09/10(水) 00:11:23.42

つか値の範囲が有限なら計算量にminmaxがかかるやろ
N支配的で見るのやめろ

**仕様書無しさん** · 2025/09/10(水) 00:38:51.03

クイックセレクトの最悪はn^2じゃん
ちょっと変えるだけで決定的になるのが面白いねという話

**仕様書無しさん** · 2025/09/10(水) 00:51:18.64

median of medians使えよ

**仕様書無しさん** · 2025/09/10(水) 00:54:30.79

お前の手口でもnlogminmaxとかにはなるんじゃね

**仕様書無しさん** · 2025/09/10(水) 00:57:31.84

上のビットから見るな
下のビットから見なさい

**仕様書無しさん** · 2025/09/10(水) 00:59:39.65

radixsortやんけ

**仕様書無しさん** · 2025/09/10(水) 01:01:19.97

binarytrieを動的に作りゃnlognか
すまんガイジ難しくね

**仕様書無しさん** · 2025/09/10(水) 01:19:59.23

上位ビットに憧れるのをやめればいい(long longではなくintを使いなさいの意)

**仕様書無しさん** · 2025/09/10(水) 02:29:09.78

天野くんのはすっごい硬い

**仕様書無しさん** · 2025/09/10(水) 10:47:36.66

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

**仕様書無しさん** · 2025/09/10(水) 10:48:08.52

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

**仕様書無しさん** · 2025/09/10(水) 10:50:01.36

割と自明な解が存在したわ
俺ガイジですありがとう
https://x.com/kiri8128/status/1965578825431195726?t=HP9YvBSwG765LyPfdLwiXA&s=19

**仕様書無しさん** · 2025/09/10(水) 10:56:50.96

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

**仕様書無しさん** · 2025/09/10(水) 11:08:36.74

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

**仕様書無しさん** · 2025/09/10(水) 11:10:58.96

値を√w個の√w文字列に分割とかすりゃいけんじゃね知らんけど

**仕様書無しさん** · 2025/09/10(水) 11:12:54.77

アルゴリズムの話はGPTとしてろよ

**仕様書無しさん** · 2025/09/10(水) 11:13:31.25

しょーもな

**仕様書無しさん** · 2025/09/10(水) 11:14:18.72

アルハラやめろ😡

**仕様書無しさん** · 2025/09/10(水) 11:14:40.88

アルゴリズムか右手と戯れることしかできない人間

**仕様書無しさん** · 2025/09/10(水) 11:17:32.16

デアスレ！？

**仕様書無しさん** · 2025/09/10(水) 11:17:51.35

スレ間違えてないか？

**仕様書無しさん** · 2025/09/10(水) 11:32:25.10

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

**仕様書無しさん** · 2025/09/10(水) 11:36:58.91

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

**仕様書無しさん** · 2025/09/10(水) 11:40:32.11

wをよしなに選べばo(nlogminmax)になるやろけどめんどくせどうせクソ遅いやろ普通にソートしろ

**仕様書無しさん** · 2025/09/10(水) 11:40:38.87

アルゴリズムの話やめよ
くんの話しよう

あぁくんくんっくんっくくくんくんくんくくんくくんくんんんんん

**仕様書無しさん** · 2025/09/10(水) 11:41:21.88

昔授業でクイックソートの実行時間計ったけどめちゃくちゃ早いよなあれ

**仕様書無しさん** · 2025/09/10(水) 12:02:24.64

11011111101010010 みたいなバイナリのソート方法を考えるとインコでもクイックソートが空で書けるようになるのでおすすめ

**仕様書無しさん** · 2025/09/10(水) 12:06:31.30

普通にpdqsort使えよ

**仕様書無しさん** · 2025/09/10(水) 12:17:08.08

大学生活　ずっと一人　だったなあ
ジェネジェネルシルシ👽🤡👽🤡
いばしょ🧸　いばしょ🧸

**仕様書無しさん** · 2025/09/10(水) 12:21:07.32

競プロerはアルゴリズムに詳しいフリしてるくせに、
近代のソフトウェアで重要なコンセンサスアルゴリズムどころか、B-treeすらまともに実装できない

やはり競プロerは役に立たない

**仕様書無しさん** · 2025/09/10(水) 12:22:26.38

ここで言ってるコンセンサスアルゴリズムは、Paxos類似のアルゴリズムのことな

**仕様書無しさん** · 2025/09/10(水) 12:25:32.29

レートが上がるならやるが

**仕様書無しさん** · 2025/09/10(水) 12:35:12.38

入りたい
シュウ酸でいいなんて

Microsoft、世界の従業員に週3日出社義務付け　2026年以降
https://asahi.5ch.net/test/read.cgi/newsplus/1757473735/

**仕様書無しさん** · 2025/09/10(水) 12:36:49.83

どうせキーエンスだろ席足りないんだろ

**仕様書無しさん** · 2025/09/10(水) 12:58:37.59

Paxosムズすぎ

**仕様書無しさん** · 2025/09/10(水) 13:17:11.67

Raftがいい

**仕様書無しさん** · 2025/09/10(水) 13:51:59.40

卒業から随分経つのにシュウ酸（COOH）2ってすぐ思い浮かんだぜ
もしやわし記憶力いい？！

**仕様書無しさん** · 2025/09/10(水) 14:16:50.80

メモリの無駄遣い

**仕様書無しさん** · 2025/09/10(水) 14:26:49.04

Twitterで仲間だなって思ってた人がオンサイトで普通の人だと悲しい
ASD仲間だと思ったのに

**仕様書無しさん** · 2025/09/10(水) 14:28:32.12

信頼できるジェネルシをみつけなさい

**仕様書無しさん** · 2025/09/10(水) 16:10:52.69

マスくんみたいなホンモノ以外は信用するな

**仕様書無しさん** · 2025/09/10(水) 17:46:56.34

低知能じゃジェネルシとは言えない

**仕様書無しさん** · 2025/09/10(水) 18:08:35.27

最悪のキメラいいますん

**仕様書無しさん** · 2025/09/10(水) 18:16:19.78

マスくんは高知能だけどな
勝手にメンヘラ発動して堕ちていかなければ競プロで黄コーダーくらいにはなれたぞ

**仕様書無しさん** · 2025/09/10(水) 18:58:48.86

マスくんは賢い

**仕様書無しさん** · 2025/09/10(水) 19:14:36.62

imosジュニア賢すぎる
ガチのポテ銀だろ
https://x.com/imos/status/1965717894563832022

**仕様書無しさん** · 2025/09/10(水) 19:23:59.99

どういうこと？

息子氏と楽しく会話しようと思って「週末は1進数を使って問題解いたんだよね。1進数ってどんなのだと思う？」って聞いたら「個数で表すってこと？」ってすぐ返事が返ってきて会話が終了した。

**仕様書無しさん** · 2025/09/10(水) 19:35:33.44

1進法だから数字をひとつしか使えない
10進法の5を表したい場合は00000とか11111と表現して個数で表す事を言っているのでは

**仕様書無しさん** · 2025/09/10(水) 19:40:43.33

1進数って0と1の区別つくん

**仕様書無しさん** · 2025/09/10(水) 19:50:56.62

そもそも1進数に1と0はない

**仕様書無しさん** · 2025/09/10(水) 19:52:16.40

>>575
imosジュニアよりも知能低いのかわいそう

**仕様書無しさん** · 2025/09/10(水) 19:52:39.34

>>675
間違ってて笑う
imosジュニアよりも知能低いの可哀想

**仕様書無しさん** · 2025/09/10(水) 19:52:54.19

どうせTKNDKSのレールを歩むんだろうなあ

**仕様書無しさん** · 2025/09/10(水) 19:53:08.24

>>678
視力低いの可哀想

**仕様書無しさん** · 2025/09/10(水) 19:53:22.48

遺伝支配的というわけ

**仕様書無しさん** · 2025/09/10(水) 19:56:44.61

10進数の1と0に決まっとるやろがクソガイジが死ねや

**仕様書無しさん** · 2025/09/10(水) 19:56:45.45

675は正しいだろ

**仕様書無しさん** · 2025/09/10(水) 20:01:52.12

00000だけでよくね？

**仕様書無しさん** · 2025/09/10(水) 20:06:24.49

これは恥ずかしい

679: 仕様書無しさん sage 2025/09/10(水) 19:52:39.34
>>675
間違ってて笑う
imosジュニアよりも知能低いの可哀想

**仕様書無しさん** · 2025/09/10(水) 20:07:20.86

スレがインコパークと化してて終わってるな

**仕様書無しさん** · 2025/09/10(水) 20:08:09.82

競プロのやりすぎで2進数と混同してるのかも

**仕様書無しさん** · 2025/09/10(水) 20:08:34.53

世代交代定期
老人死んでね

**仕様書無しさん** · 2025/09/10(水) 20:24:59.75

結局遺伝子

**仕様書無しさん** · 2025/09/10(水) 20:40:47.70

遺伝子のインコの部分

**仕様書無しさん** · 2025/09/10(水) 20:42:11.29

イ伝子(はずれ)

**仕様書無しさん** · 2025/09/10(水) 20:43:32.21

遺伝子の亻はインコのイ

**仕様書無しさん** · 2025/09/10(水) 20:45:54.44

一億総インコ社会　インコ忖度のおしまい国家　やめてね

**仕様書無しさん** · 2025/09/10(水) 20:46:13.21

incoジュニアというわけか

**仕様書無しさん** · 2025/09/10(水) 20:46:44.59

imosジュニアに生まれたかった

**仕様書無しさん** · 2025/09/10(水) 20:48:35.57

遺伝子のイン子の部分

**仕様書無しさん** · 2025/09/10(水) 20:50:02.77

全てが繋がってるな
このスレこの世の本質しか記述されていなくてすごすぎる

**仕様書無しさん** · 2025/09/10(水) 20:50:20.96

デが欠けるとインコになってしまうわけね
デアスレ開始

**仕様書無しさん** · 2025/09/10(水) 20:57:22.50

遺伝子からデを抜くとイン子！

**仕様書無しさん** · 2025/09/10(水) 21:29:21.62

デアスレのassの部分

**仕様書無しさん** · 2025/09/10(水) 23:05:41.56

トランプは関税とイスラエル支持で狂い続けてるし、
イスラエルはイランやカタール攻撃してるし、
ロシアはポーランドを攻撃し始めた
中国はハイペースで世界中から原油を備蓄し始めた

これはもう世界大戦だね
今度こそグレートリセットまで秒読みか

**仕様書無しさん** · 2025/09/10(水) 23:07:15.61

中国がハイペースで原油備蓄、世界的余剰吸収
https://news.yahoo.co.jp/articles/4232d9367ba29c96ca7ae1fca2f01334c486b96e

ポーランド軍がドローン撃墜、ロシアが繰り返し領空侵犯
https://www.asahi.com/articles/AST9B1DN6T9BBQBQ1YSM.html

**仕様書無しさん** · 2025/09/11(木) 09:18:50.04

流石は日本一の松尾研だ

**仕様書無しさん** · 2025/09/11(木) 09:59:23.69

【速報】火星の岩石から生命の痕跡か、NASA発表
https://www.47news.jp/13137559.html

**仕様書無しさん** · 2025/09/11(木) 10:21:26.86

火星にいるのは、タコなのか、Gなのか

**仕様書無しさん** · 2025/09/11(木) 10:42:48.11

ksとtk定期

**仕様書無しさん** · 2025/09/11(木) 10:56:44.73

KS、TK、G、なるほどな
宇宙人であるイーロン・マスクが火星を目指すわけだ
すべてこのスレに書かれていたことだな

**仕様書無しさん** · 2025/09/11(木) 10:59:47.00

ガチのマジで、アカシックレコードすぎるだろ
全ては競プロに通ずというわけ
競プロは人生そのもの
競プロ界隈は社会そのもの

この世の真理を知りたければ、
過去スレ精進、しなさい。

**仕様書無しさん** · 2025/09/11(木) 11:02:58.26

出身中学を問へと繰り返してるのはそういうこと
宇宙人が透けるから👽

**仕様書無しさん** · 2025/09/11(木) 11:12:01.58

火星で宇宙人を発見せよ

**仕様書無しさん** · 2025/09/11(木) 11:12:45.63

競プロスレでもなんでもない

**仕様書無しさん** · 2025/09/11(木) 11:14:08.66

開成の火星の部分

**仕様書無しさん** · 2025/09/11(木) 11:14:35.70

赤マスさんみたいな人はバックギャモンや人生ゲームみたいなボードゲームも強くなるの？

**仕様書無しさん** · 2025/09/11(木) 11:15:31.75

上を見るな、下だけを見ろ

**仕様書無しさん** · 2025/09/11(木) 11:15:35.03

火星ですから

**仕様書無しさん** · 2025/09/11(木) 11:15:49.20

上(天体)

**仕様書無しさん** · 2025/09/11(木) 11:17:21.66

人は空ばかり見てる
地上の星を見てるのインコだけ

**仕様書無しさん** · 2025/09/11(木) 11:19:38.75

In conclusion, のインコの部分

**仕様書無しさん** · 2025/09/11(木) 11:20:19.68

嫉妬インコのshitの部分

**仕様書無しさん** · 2025/09/11(木) 11:24:13.96

in common定期

**仕様書無しさん** · 2025/09/11(木) 11:25:30.12

commonなインコ問

**仕様書無しさん** · 2025/09/11(木) 11:26:05.96

デアスレデトックス

**仕様書無しさん** · 2025/09/11(木) 11:31:51.35

ジェネルシのgenerostiy