競技プログラミングにハマるプログラマのスレ 145
■ このスレッドは過去ログ倉庫に格納されています
高橋洋翔は数学検定1級に最年少で合格し小6で数学オリンピックの予選通過
KS在籍
両親はUT >>311
競プロerじゃんこの人
jmo本選まで行ってる >>318
この人は中三でjoi本選優秀賞まで行ってる 「JOl 梶田光 」「JOI 高橋洋翔」で調べるとちゃんと出てくるね
隠れ競プロer多いな 今日も競プロer以外をageて自分をボコボコにした競プロerに復習するぞお！→普通に競プロerでした
最近このタイプのager負けパターン増えてきたな 普通にage続ければいいのに競プロerだと発覚した瞬間涙目敗走してageなくなるの笑う ヤリチンだと発覚した瞬間童貞が敗走するようなものだな 12月27日は、ヨハン・ベルヌーイの兄でスイスの数学者のヤコブ・ベルヌーイの誕生日です🎂 ベルヌーイ数 形式的べき級数 でググったら山ほど出てくるじゃん ベルヌーイ数の発見の経緯はそのまんまΣi^kについての研究だぞ >>329
だいたい全部似たような記事だけどなんか別のアプローチから導出できたりする？ 総和公式で出てきて、母関数を簡潔に記述できる以外は知らん exp(x)と畳み込むと、自分自身にxを足したものになるってことだよね
なんらかの解釈ができそう ググればわかることだとしても、それを話に出さないでゴシップネトストトークするよりずっとましではある >>334
ミス、exp(-x)と畳み込むと、自分自身からxを引いたものになる、だった あれ、ベルヌーイ数の母関数をxexp(x)/(exp(x)-1)にしてるやつと、x/(exp(x)-1)にしてるやつがあるな
それで混乱した >>338
x/(exp(x)-1)の流儀しか見たことないぞ https://37zigen.com/linear-sieve/
この記事の「線形篩を用いた冪数の列挙」の計算量はO(N * log m / log N)ってなってるけど、素数に対してくり返し２乗法したときの計算量O(logK)がかかってなくね？
それ考慮したらO(N*logm * log k / logN)じゃね？ O(Nlog m/log N)でN以下の素数を列挙済とする
素数定理からN以下の素数自体の数はO(N/log N)
k乗の前計算は、各素数に対して行うので、O(Nlog k/log N)
オイラーの定理からk≦mの場合に帰着できて、結局、O(Nlog m/log N)ということなのかな？ >>342
あ、最初の1行目は、O(Nlog m/log N)じゃなくてO(N)ね 最小素因数を高速に求めるパートとか普通に知らなかったわ
ガイジスレ精進助かる インコなのでこの記事を見てようやく>>274の意味が理解できた よく読むと誤植で
x^k mod m
を繰り返し二乗法したときの計算量がO(logk)であるべきところ、O(logm)になっている 誤りではないので、誤植かどうかは微妙なところだが、繰り返し二乗法のパートをO(log m)でカウントしてるのだと思う 最小素因数をメモるテクは蟻本でみて知ってたけど、それを線形篩と言うのは知らなかったな わざわざO(logm)と書くのは数学界隈からのクソリプ避け 蟻本にあったのか
また自分が蟻本を全然理解してないことがわかってしまったな 正直競プロ強くても薄給サラリーマンにしかなれないからコスパ悪いよな if p * d > N or p > lpf[d]:
break
の部分が地味に賢い
こういうのを息を吸うように自力で思いつきたい 蟻本はレート低いときに読むとついいろいろ読み飛ばしちゃうよな
レート上げて再読するときが本番 暖色目指すより、研究やって国際学会で発表したほうがタイパいいよな 橙ぐらいでも蟻本で新しい発見あると言ってたし、10年ぐらい前の本なのにすごい 数論系結構後回しにしてしまうので、たまにコンテストに出てきていつもやられる floor sumとかACL出る前どのぐらいの人が知ってたんだろうね ごめんなさい、蟻本で線形篩を見た気がしたので349のようなレスをしてしまったんですが、今見てみたら載ってなかったです。マジのデタラメでした。でも蟻本見ると学びがあるのはマジだと思います。 ガイジスレに書き込んでる奴がコスパを語るな定期
そもそもコスパ考えてやるようなゲームじゃないし まあ、載ってても全然不思議ではないと思わせる力が蟻本にはあるので、そういう偽の記憶が作られるのも無理はない 最大素因数列挙の部分がよくわかっていない
かならいさんとの議論のところ コスパ爺はager本人か、agerに極めて近いパーソナリティを持つ引きこもりだから、レスを意訳すると「難しいデアの話なんて全然わからないから俺に構ってくれえええええ😭俺だけを見てくれええええええ😭」って意味だよ
ほら、構ってあげたから喜んでね コスパ爺本人はレートが低いだけでなく低学歴で、まともな研究実績・開発実績もないのが笑いどころ
ただの低知能の嫉妬というかなんならagerだろ そもそも線形篩とエラトステネスは実用上定数倍差の範疇だし
じゃあ最大素因数列挙は理解せずともエラトステネスの篩でもいいのか 大昔線形篩ライブラリ化したけど結局遅くなったんだよな でも、簡単に素因数を一個高速で導出できるとi^k列挙でも役に立つし、素数列挙以外でも結構応用がありそうな技術に見える floor sum自体は未だに謎技術感が拭えないけど、一応役に立つ問題はちらほらある（ACLにあるから出題されてるのでは？感もあるが…） 線形篩周りは面白いテクだけど、競プロだと区別不能なんじゃないかなあと思う aclの意義、遅延セグ木を出しまくれるようになったこと（AtCoderにはライブラリゲーは良問になりにくいという思想があるので） floor sum, 直線と格子点の数の関係でイメージしてるけどこれが役に立つ問題あまり解いたことないな
ちょっと前のABCのGとExで1回ずつ見た気がするが CHTとか凸包(幾何系)もだいぶライブラリ力が大事な気がするけど、なんで入れないんだろ floor sumは値側から√N個愚直、答え側から√N個区間を計算すればO(√N)
と思ってみにいったらlogオーダーでくそわろた ライブラリ整備したからCHTやるだけ問題また来てくれ ACLの2-SATライブラリも使ったことないな
ほぼ同根のSCCライブラリは結構使い所あるが(SCCしてトポソ、DPなど) 競技プログラミングやってたけどつまらなくて茶タッチでやめた
こっちでソシャゲやってた方がコスパいいことがわかった 黄色タッチまではやったうちに含まれないし、そこまで楽々いけない時点で低知能確定なのではい 八問ABCだとGとEx枠に出てくる感じ
2-SATは普通に情報系の基礎教養として知っといていい話だと思うが 2-SAT、3-SATこそNPとか計算量周りの話で一番大事なところだから大学の講義で絶対やるだろ たとえFランでも情報系なら >>391,392
2SAT使う青diffの問題なんてなくね？仕組みは青でも理解できるものだけど 2-SATななんならセグ木やBITより基礎教養感強いな
まあ、人間ならどっちも勉強して理解しとけという話ではあるが ABCで勝つためには黄diff橙diff解けるように練習すべきなのに、青diff問題がないからやる必要がないと思ってるのか？ >>404
ABC-G以前で出題されたの見たことないんだけど、青レベルならそういう典型身につける前にやるべきことがあるのでは >>402
じょえちゃんねるのドッキリが不成立になり謝罪動画が投稿される >>399
でも青色が黄diff倒せないと辛くないか 自分の中で青というと1800〜1999ぐらいを想像するというのがあるな 純粋培養に教えてやるけど、3-SATに帰着させることで多くの問題が多項式時間で解けないことが示されてるからな
これをインコに理解させるのは難しいかもしれませんが >>408
2-SAT使う黄色diff問題ってどれ ■ このスレッドは過去ログ倉庫に格納されています
