まとめの限定公開に「リンク限定」が追加されました。URLを伝えてまとめを共有しよう!
1
Kawazoe @riverplus
CodeIQ「スパイラル・ウォーク」問題、明日で公開終了です。期間が終わったら、ぜひ皆さまのコードを共有して下さい。Togetterでまとめます! codeiq.jp/q/3053
Min_25 @min_25_
約数の個数の総和を O(N^{1/3+}) 程度で計算して G(10^19) で 0.6 秒ぐらい: ideone.com/lZnZTU 「スパイラル・ウォーク」問題 codeiq.jp/q/3053 @riverplus @codeiq
Kawazoe @riverplus
なんだこりゃあ! イミフすぎてやばい。目がテン。 twitter.com/min_25_/status…
しなうさん @shinau3
@riverplus これが模範解答なんですね(白目)
Kawazoe @riverplus
@shinau3 √nより小さくするのはふつうに無理と思ってました・・
idiotton @idiotton
@riverplus 凄まじいのを見ちゃうと、なんだかアレですが、普通に普通に。 ideone.com/OPElLu
Kawazoe @riverplus
@min_25_ スーパーな解ありがとうございました。この1からNまでの約数の個数の総和を求めるやり方って、一般に知られたやり方なんでしょうか?
Min_25 @min_25_
@riverplus 自分のコードは Euler 540 の Forum 由来なので、Euler 勢には知られていそうです。O(n^1/3) の論文としては arxiv.org/abs/1009.3956arxiv.org/abs/1206.3369 を見たことがあります。
Kawazoe @riverplus
@min_25_ ありがとうございます。論文、ぱっと見て分かるような代物ではなかったですが、頑張れば意味わかるかな・・
Min_25 @min_25_
@riverplus こちらこそありがとうございます。 自分も論文の詳細はよくわかっていないです。誰かがこれらの論文を元に実装していると心強いのですが…。
Kawazoe @riverplus
約数の個数の和を高速に求める例の論文、少し眺めてみたけど、さっぱり。双曲線を折れ線で近似しつつ、両者の間の領域にある格子点をイイ感じに計算してるみたい。
angel as ㌵㌤の猫 @angel_p_57
@riverplus ということで、スパイラル・ウォーク、私のはnaiveにRuby(39)。 2.upto(m=1-s=-gets.to_i){|i|s+=m/i};p s Ο(√n)よりはやい高速化は断念しました。
🅲🅸🅰🆁🅰🅽🅰 シアラナ @cia_rana
@riverplus 多分O(√n)の人と同じコードです。一応golf(Ruby(41))もやってますがイマイチ。。。 bitbucket.org/snippets/cia_r…
pylab @_pylab_
ideone.com/lj03Aa 「スパイラル・ウォーク」問題 codeiq.jp/q/3053 @riverplus python 3 普通のアルゴリズム。計算回数2*N^(1/2)くらい
nekoTheShadow @neko_the_shadow
CodeIQ 「『スパイラル・ウォーク』問題」に参加しました。 by @neko_the_shadow on @Qiita qiita.com/neko_the_shado…
htlsne @htlsne
@riverplus あんまり速くないですが、私のコードです gist.github.com/htlsne/d513678…
Liberdade @LiberJP
@riverplus CodeIQ スパイラル・ウォーク解答 ideone.com/rh3bdA コードだけだとあとで見返して自分で意味わからんくなりそうだったので、コメントでなにをやったか書いたらコメントのほうが長くなった
haruya @haruya1212
CodeIQ「スパイラル・ウォーク」問題 @riverplus sieving で O(N log log N)。今回やらかしてしまった。 ideone.com/kZ6xwQ
ログインして広告を非表示にする
ログインして広告を非表示にする