CodeIQ「スパイラル・ウォーク」問題、明日で公開終了です。期間が終わったら、ぜひ皆さまのコードを共有して下さい。Togetterでまとめます! codeiq.jp/q/3053
2016-12-21 21:51:15@riverplus (ΦωΦ)<スパイラル・ウォークです yuppe19.bitbucket.io/3053_spiral_wa…
2016-12-22 10:47:39解説付きコード公開。ideone.com/axXSo8 @riverplus @codeiq twitter.com/riverplus/stat…
2016-12-22 12:21:20約数の個数の総和を O(N^{1/3+}) 程度で計算して G(10^19) で 0.6 秒ぐらい: ideone.com/lZnZTU 「スパイラル・ウォーク」問題 codeiq.jp/q/3053 @riverplus @codeiq
2016-12-22 20:44:01@min_25_ スーパーな解ありがとうございました。この1からNまでの約数の個数の総和を求めるやり方って、一般に知られたやり方なんでしょうか?
2016-12-23 10:51:51@riverplus 自分のコードは Euler 540 の Forum 由来なので、Euler 勢には知られていそうです。O(n^1/3) の論文としては arxiv.org/abs/1009.3956 と arxiv.org/abs/1206.3369 を見たことがあります。
2016-12-23 13:35:11@riverplus こちらこそありがとうございます。 自分も論文の詳細はよくわかっていないです。誰かがこれらの論文を元に実装していると心強いのですが…。
2016-12-23 23:17:15約数の個数の和を高速に求める例の論文、少し眺めてみたけど、さっぱり。双曲線を折れ線で近似しつつ、両者の間の領域にある格子点をイイ感じに計算してるみたい。
2016-12-24 19:24:59@riverplus ということで、スパイラル・ウォーク、私のはnaiveにRuby(39)。 2.upto(m=1-s=-gets.to_i){|i|s+=m/i};p s Ο(√n)よりはやい高速化は断念しました。
2016-12-22 23:54:43@riverplus 多分O(√n)の人と同じコードです。一応golf(Ruby(41))もやってますがイマイチ。。。 bitbucket.org/snippets/cia_r…
2016-12-23 00:20:27ideone.com/lj03Aa 「スパイラル・ウォーク」問題 codeiq.jp/q/3053 @riverplus python 3 普通のアルゴリズム。計算回数2*N^(1/2)くらい
2016-12-23 01:13:03CodeIQ 「『スパイラル・ウォーク』問題」に参加しました。 by @neko_the_shadow on @Qiita qiita.com/neko_the_shado…
2016-12-23 01:53:42@riverplus CodeIQ スパイラル・ウォーク解答 ideone.com/rh3bdA コードだけだとあとで見返して自分で意味わからんくなりそうだったので、コメントでなにをやったか書いたらコメントのほうが長くなった
2016-12-23 15:40:08CodeIQ「スパイラル・ウォーク」問題 @riverplus sieving で O(N log log N)。今回やらかしてしまった。 ideone.com/kZ6xwQ
2016-12-24 21:20:03