[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
798(1): デフォルトの名無しさん [sage] 2023/06/16(金) 21:29:35.35 ID:FhD4SiQz(1/4) AAS
>>797
797(2): デフォルトの名無しさん [] 2023/06/16(金) 20:29:55.57 ID:2udbfubS(1/2) AAS
>>738
外部ﾘﾝｸ:paiza.io
細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた
総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる
解説プリーズ
コード読んでもさっぱりわからん
どうやってO(N)にできたんですか？
799: デフォルトの名無しさん [sage] 2023/06/16(金) 21:34:18.18 ID:FhD4SiQz(2/4) AAS
アレ？
やっぱりこれ三乗してるんじゃないの？
O(N)ちゃうやん
O(N)の意味わかってる？
801: デフォルトの名無しさん [sage] 2023/06/16(金) 21:36:46.05 ID:FhD4SiQz(3/4) AAS
イヤ、整数計数の多項式環の三乗もfftで早くできるのかな？
802: デフォルトの名無しさん [sage] 2023/06/16(金) 21:41:30.83 ID:FhD4SiQz(4/4) AAS
もしかしたらできるか
fftのアルゴリズムってこっちのコンボリューション積をあっちの各点積に持っていく方法だから多項式環でもできるんかな？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.039s