X

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

■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2023/12/27(水) 17:54:03.32
競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
競技プログラミングにハマるプログラマのスレ 140
https://medaka.5ch.net/test/read.cgi/prog/1702350568/
競技プログラミングにハマるプログラマのスレ 141
https://medaka.5ch.net/test/read.cgi/prog/1702735806/
競技プログラミングにハマるプログラマのスレ 142
https://medaka.5ch.net/test/read.cgi/prog/1702969685/
競技プログラミングにハマるプログラマのスレ 143
https://medaka.5ch.net/test/read.cgi/prog/1703141733/
競技プログラミングにハマるプログラマのスレ 144
https://medaka.5ch.net/test/read.cgi/prog/1703346239/
0191仕様書無しさん
垢版 |
2023/12/27(水) 22:35:58.32
東大受かったけど明治理工落ちた
明治理工難関すぎる
0192仕様書無しさん
垢版 |
2023/12/27(水) 22:40:35.85
東大受かったなら原因は学力ではないのは確かだな
カンニング発覚でもしたのか？
0194仕様書無しさん
垢版 |
2023/12/27(水) 22:41:43.23
>>188
暖色の中なら平均くらいじゃね？
黄橙だともっと出来ない奴ざらにいそうだし
0196仕様書無しさん
垢版 |
2023/12/27(水) 22:44:40.19
東大模試数学半分取るだけなら大して難しくなくない？
安定して数学半分以上ならまあ
0200仕様書無しさん
垢版 |
2023/12/27(水) 22:56:46.13
>>197
東大受けてないんじゃなかった
東工大＆早慶理工落ちって言っていた気がする
0201仕様書無しさん
垢版 |
2023/12/27(水) 23:01:01.16
>>194
センター5割とかでも過学習すれば黄色タッチくらいはいけそう
0203仕様書無しさん
垢版 |
2023/12/27(水) 23:02:54.81
>>201
高校時代どれくらい勉強にリソースを割いてたかにもよるけど、センター5割って茶緑で一生停滞してるレベルだろ
0204仕様書無しさん
垢版 |
2023/12/27(水) 23:05:02.03
正直未成年飲酒とかどうでもいいレベルの話というのが社会典型だけど、嫌われてるやつはちょっとの瑕疵でも叩かれまくるというのも社会典型なので
0205仕様書無しさん
垢版 |
2023/12/27(水) 23:05:33.70
センター五割って受験勉強全くしなくても取れそうだな
0207仕様書無しさん
垢版 |
2023/12/27(水) 23:06:09.68
ガチれば東大
ガチれば黄タッチ
灰レート仕草やめろ
0208仕様書無しさん
垢版 |
2023/12/27(水) 23:06:20.46
TKなら普通に授業受けてればとれるんじゃないの？
0209仕様書無しさん
垢版 |
2023/12/27(水) 23:06:38.61
逆に黄橙なら東大数学八割超えがざらにいるだろ
その意味でchkdは異常に数学できないぞ
0210仕様書無しさん
垢版 |
2023/12/27(水) 23:08:47.66
jmo予選って証明書かないし算数パズルの範疇だろって思うんだが、本当に感覚派なんだな
0211仕様書無しさん
垢版 |
2023/12/27(水) 23:08:55.07
高校数学の異常過学習者と比較するのはかわいそうだとおもった
0212仕様書無しさん
垢版 |
2023/12/27(水) 23:09:50.00
異常過学習なんてしなくても東大数学八割取れる定期
0214仕様書無しさん
垢版 |
2023/12/27(水) 23:11:22.30
JMO予選落ち and 東大数学六割 and FPS程度の数理の勉強すら放棄、はちょっと擁護できないレベルの数弱ですね
0217仕様書無しさん
垢版 |
2023/12/27(水) 23:17:58.74
試験場だと緊張するけど自室のパソコンの前でカタカタやる時は異常に集中できるとか
パーソナリティ由来の特性は色々あるじゃろ
0218仕様書無しさん
垢版 |
2023/12/27(水) 23:18:36.46
chokuはちゃんと対策していればjmo予選通過はできたと思うと言っていたはず
0220仕様書無しさん
垢版 |
2023/12/27(水) 23:19:33.38
chokudaiも鉄に行ってればもう少し、みたいに書こうとして検索したら通ってたの吹いたわ

やはり中受支配的と言うより鉄支配的だな高受でも鉄なら完全にメインストリーム
0221仕様書無しさん
垢版 |
2023/12/27(水) 23:19:47.04
才能はあるけどやる気がないのがckdiで対策系の技能を悉く落としてる
0222仕様書無しさん
垢版 |
2023/12/27(水) 23:21:28.20
競プロの学習負荷が他の勉強と比べて低すぎるからな
0224仕様書無しさん
垢版 |
2023/12/27(水) 23:22:36.92
鉄通っててそれだけ才能あるのに、受験数学も数オリ数学もできなさすぎて、全く努力してないことが透けるな
0227仕様書無しさん
垢版 |
2023/12/27(水) 23:24:42.42
なんつーか座学が嫌いなんだろchokuは
競プロは死に覚えゲーって言ってるし、ゲームとか会社経営は出来るわけだし
たぶん毎週模試があったら受験力も強くなってたタイプだと思う
0228仕様書無しさん
垢版 |
2023/12/27(水) 23:25:14.58
普通に受験、数オリ強者がたくさんいる東大、京大、東工大の方が強くて、受験と独立した能力を測る慶應スーパーファミコンは基本的に相性悪い
単にcnkdiが異常者
0229仕様書無しさん
垢版 |
2023/12/27(水) 23:26:12.42
ckdiのポジショントークはコンプレックスの裏返しかな
0233仕様書無しさん
垢版 |
2023/12/27(水) 23:49:39.32
Σ[1≦k≦n]k^Nをnの多項式で表した時の各項の係数mod998244353ってO(N)で求められる？
0234仕様書無しさん
垢版 |
2023/12/27(水) 23:51:25.09
>>193
これ地学選択に対する風評被害すぎる
0238仕様書無しさん
垢版 |
2023/12/28(木) 00:03:57.72
マータFPS
デア厨がよぉ
ラグランジュ補間の方、評価するための点を求めるためにO(KlogK)かかってね、
0239仕様書無しさん
垢版 |
2023/12/28(木) 00:05:32.75
>>236
なるほどサンクス
ラグランジュ補間の方O(K logp)なのよく分からんな
ぱっと見logつきそうに見える
0241仕様書無しさん
垢版 |
2023/12/28(木) 00:10:06.91
agerなら原神とか変態性欲系のキモオタコンテンツ出してくるから違うね？
0242仕様書無しさん
垢版 |
2023/12/28(木) 00:14:32.52
この系統のラグランジュ補間、xが負の数の点をいれたら定数倍高速化できないかって思ったが、多項式と整合的にxが負のときの値求めるの無理か
0243仕様書無しさん
垢版 |
2023/12/28(木) 00:22:47.11
ファウルハーバーの公式とラグランジュ補間組み合わせればO(K+logp)かと思ったが、ベルヌーイ数の導出が律速になって終わりそう
ベルヌーイ数埋め込めばいける？
0244仕様書無しさん
垢版 |
2023/12/28(木) 00:27:04.09
ベルヌーイ数埋め込んだらラグランジュ補間いらないだろ
0246仕様書無しさん
垢版 |
2023/12/28(木) 00:34:03.39
階乗が逆元含めてO(N)で求まるのなんかキモい
直感に反する
0247仕様書無しさん
垢版 |
2023/12/28(木) 00:38:01.59
🧅と運営が対立してるのを、ガイジスレで神の視点から眺めようと思ったら、🧅がchnk信者になるという予想外の展開が来てしまった
0248仕様書無しさん
垢版 |
2023/12/28(木) 00:43:33.02
>>239
うしさんの記事を見た感じ、ラグランジュ補間の方の計算量がO(K + log p)ってのは多項式の係数を求めるのじゃなくて、多項式の値を求めるときの計算量じゃない？
ラグランジュ補間で係数を求める場合O(Klog^2K)らしいし結局畳み込み必要なのはファウルハーバーと一緒だしファウルハーバーの方が計算量も実際の速さも速い気がする
0249仕様書無しさん
垢版 |
2023/12/28(木) 00:46:42.98
AtCoderの運営は🧅の会社だからな
そりゃ対立なんかしないよ
0250仕様書無しさん
垢版 |
2023/12/28(木) 00:47:36.96
ラグランジュ補間でこの問題を解くための計算量じゃなくて、ラグランジュ補間そのものの計算量っぽい
微妙な書き方だ
0251仕様書無しさん
垢版 |
2023/12/28(木) 00:51:16.78
ラグランジュ補間は係数求めないにしてもO(KlogK)かかるな
0252仕様書無しさん
垢版 |
2023/12/28(木) 00:53:23.89
ラグランジュ補間で、係数を求めずに値を求めるだけにしても、f(1),...,f(K+2)求めるのにかかるって話
0253仕様書無しさん
垢版 |
2023/12/28(木) 00:58:18.91
天才DPでドピュドピュ求められるみたいな数弱用解法ないの？
0254仕様書無しさん
垢版 |
2023/12/28(木) 00:59:43.81
半年ぶりに過去問解き直したらゴミカス実装になっていてシナシナだよ
0255仕様書無しさん
垢版 |
2023/12/28(木) 01:01:25.05
Nがクソデカだと想定すると、素朴なボトムアップでは満足なDPにはならなくて、ダブリング系か平方分割系のDPが必要そう
0257仕様書無しさん
垢版 |
2023/12/28(木) 01:12:21.29
ラグランジュ補完やるだけ出たらもう青diffとかかねえ
大昔のは試験管橙diffだけど
0258仕様書無しさん
垢版 |
2023/12/28(木) 01:12:39.96
大学の講義でもやりそうだし検索してたどり着きやすそうだし
0259仕様書無しさん
垢版 |
2023/12/28(木) 01:14:02.07
組合せ論的解釈考えてるけどベルヌーイ数がキモくてよくわからんな
0260仕様書無しさん
垢版 |
2023/12/28(木) 01:15:47.57
寒色インコだからわからないけど、えびちゃんの「えびちゃんの「Clang の k 乗和の最適化を眺める」って記事での予想によると線形篩×等比数列のときの多項式補完でO(K)でいけるかもしれないらしいね
0261仕様書無しさん
垢版 |
2023/12/28(木) 01:16:42.25
N以下の長さでK未満の非負整数で構成されている数列の通り数なのはわかるけど
0263仕様書無しさん
垢版 |
2023/12/28(木) 01:21:39.48
これか
rated出ないのはどうかと思ってるが、あんま普通に競プロやってると出てこない視点からの記事は助かる
https://rsk0315.hat
enablog.
com/entry/2023/09/19/043126
0265仕様書無しさん
垢版 |
2023/12/28(木) 01:24:03.08
開成は中受トップ校だしやっぱりポテ高めだな　
河野ですら落ちたわけだし
0266仕様書無しさん
垢版 |
2023/12/28(木) 01:25:27.25
人間(暖色)によるデアトーク　vs 話についていけない寒色インコagerの孤軍奮闘
0267仕様書無しさん
垢版 |
2023/12/28(木) 01:29:54.41
インコなのでO(NlogK)の自明ジョークしか分からない
0268仕様書無しさん
垢版 |
2023/12/28(木) 01:30:02.72
線形篩でできる話まだよくわかってないんだけど、リーマンゼータ関数とか関係あるんかな
0269仕様書無しさん
垢版 |
2023/12/28(木) 01:31:53.11
リーマンゼータ関数というかオイラー積表示の有限バージョン的な
0270仕様書無しさん
垢版 |
2023/12/28(木) 01:35:58.21
オイラー積的なアプローチ、有限和の場合うまく変換できなくて意味なさそう
0271仕様書無しさん
垢版 |
2023/12/28(木) 01:45:23.24
多分K以下の素数をO(K)で求めてそのK乗を前計算していろいろするんだけどよくわからん
今酒入ってるし明日考えるわ
0272仕様書無しさん
垢版 |
2023/12/28(木) 01:45:58.48
線形篩って使う機会ある？
osa-k法とかとは別物だっけ？
0273仕様書無しさん
垢版 |
2023/12/28(木) 01:48:33.21
知らんけど線形篩使うとi^kを1≦i≦kでO(k)で列挙できるって主張してるし
0274仕様書無しさん
垢版 |
2023/12/28(木) 02:01:11.89
O(NlogK)が自明なのにO(N)がそんなに嬉しいのか？
線形篩を使えばx^K(1<x<N, K<N)はO(N)ではある
素数は愚直にO(logK)で求めると、素数の個数はO(N/logN)個なのでK<Nの仮定からO(N)
あとは 20^K = 2^K × 10^K とかやればよいため
0275仕様書無しさん
垢版 |
2023/12/28(木) 02:04:49.14
O(KlogK)をO(K)に落とす話であって、O(NlogK)をO(N)に落とす話をしていたわけでないのだが
0276仕様書無しさん
垢版 |
2023/12/28(木) 02:09:23.15
>線形篩を使えばx^K(1<x<N, K<N)はO(N)ではある
これは列挙の話？一個だけ求める話？
0277仕様書無しさん
垢版 |
2023/12/28(木) 02:10:44.11
一個だけでいいならO(logK)で求められます
いかがでしたか？
0278仕様書無しさん
垢版 |
2023/12/28(木) 02:11:53.62
列挙のやり方がレスからわからなかったから前提を確認したかった
0279仕様書無しさん
垢版 |
2023/12/28(木) 02:13:23.84
最小の素因数を高速で求められれば簡単なDPでO(N)ということか
0282仕様書無しさん
垢版 |
2023/12/28(木) 02:22:14.62
そろそろO(N)がTLEする前提に移らせてもらってもよろしいでしょうか
0283仕様書無しさん
垢版 |
2023/12/28(木) 02:27:32.92
ラグランジュ補間を使う話が先に出てるので、1≦i≦K+2でi^KをO(K)求めるとi^Kのnまでの和(1≦n≦K+2)をO(K)で求められて、そのあとラグランジュ補間でO(K+log p)でNまでの和を求める話では？
0284仕様書無しさん
垢版 |
2023/12/28(木) 02:29:51.39
なんで急に部分的にナイーブ解の話に巻き戻ったのか謎すぎる
0285仕様書無しさん
垢版 |
2023/12/28(木) 02:47:03.92
274が単に267までしかスレよく見てなかっただけでしょ
0286仕様書無しさん
垢版 |
2023/12/28(木) 03:08:23.39
そもそもラグランジュ補間が等差数列ならO(K+log p)でできること自体知らなかったのだが
0287仕様書無しさん
垢版 |
2023/12/28(木) 03:13:56.79
そもそもラグランジュ基底多項式を用いてある一点を評価することをラグランジュ補間と一般に呼ぶのかわからん
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況