桃の天然水 このページをアンテナに追加

2017-12-08

[]Project Euler 615 Project Euler 615を含むブックマーク Project Euler 615のブックマークコメント

https://projecteuler.net/problem=615

150着。

実は、この問題は採用された最初の自作。

(内部的に言うと実は違うのだが)

14年2月に提案した問題らしい。それが最後に少し改変されて公開されるに至った。

解いてみればわかるが、手法ありきのわざとらしい問題である。

2017-09-23

[]Project Euler Dev Teamのメンバーに Project Euler Dev Teamのメンバーにを含むブックマーク Project Euler Dev Teamのメンバーにのブックマークコメント

きっかけは、Problem 12だっただろうか。私は、PriorityQueueを使えば大きな数でもこの問題が解けることに気が付いた。これがフォーラムでどこまで大きな数で1分以内に問題を解けるかの競争が行われる端緒になったのではないだろうか。

どうもこれを中の人が見ていたらしく、それ理由にあったらしい。問題も提出していてなかなか採用されなかったが、貢献が認められたようだ。16日承諾してメンバーになった。

当然ながら、fastest solversに入る競争はできなくなる。100人埋まってからは解答できるので、間違えないか心配だ。

2017-09-01

[]Project Euler 29 Project Euler 29を含むブックマーク Project Euler 29のブックマークコメント

http://projecteuler.net/index.php?section=problems&id=29

この問題は、解くだけなら非常に易しいです。Pythonなら1行で書けるレベルです。

しかし、工夫をすれば大きな数でも解けることに昔気づきました。フォーラムに今までそういう書き込みは無かったのでそのような解法を書き込むと、Kudos(いいねみたいなもの)がたくさん付くも、なぜか委員会に認められずに、自動消去されるという憂き目に。

さて、おさらいしておきましょう。

ab(2 <= a, b <= N)は(N-1)2個ありますが、同じ値を取る(a, b)の組み合わせがあるために問題が成り立つのですね。ここでは、より小さい底(a)で同じ値になる組合せをカウントして、(N-1)2から引きます。

例えば、N=10で考えます。より小さい底になるのは、

a=4のとき、

42 = 24, 43 = 26, 44 = 28, 45 = 210

ここまでの4つです。次は、46 = 212となって、指数が10を超えてしまうからです。

a=8のときは、2つの底2, 4を考えられて、

82 = 26, 83 = 29
82 = 43, 84 = 46, 86 = 49

の5つですが、82がダブっているので、4つですね。

a=9のとき、

92 = 34, 93 = 36, 94 = 38, 95 = 310

の4つです。

ここで、分かるのは、4と9は全く同じということです。つまり、同じ指数なら1回計算すればよく、あとは同じ指数がいくつあるか数えればいいだけです。例えば、指数2は、int(sqrt(N))-1からべき乗数を引いた数なので、簡単に再帰的に求められます。

それから、底が小さくなるのは、もちろんべき乗数のときです。このようにすれば、O(N(logN)^2)程度の計算量になると思います。

ここまでは復習で、ここからが本番です。さきほどのa=8のとき、上の段と下の段のそれぞれの個数は簡単に求まります。しかし、重複があるので難しくなるわけです。もう少し見やすくするために、N=20で見て見ましょう。

82 = 26, 83 = 29, 84 = 212, 85 = 215, 86 = 218
82 = 43, 84 = 46, 86 = 49, 88 = 412, 810 = 415, 812 = 418

8の指数は、上の段は1刻みで[2, 6]の範囲、下の段は2刻みで[2,12]なので、どちらも5つあります。そして、どちらにも含まれるのは、2刻みで[2,6]の範囲なので、3つです。つまり、指数3のべき乗数が底のとき、5+5-3=7つの指数で底が小さくなり得ることになります。

これを一般化すると包除原理を使うことになります。そして、いつものように分割統治法を使います。しかし、このままだと分割統治法を使う意味があまりないので、ある程度まとめた計算をしなければなりません。このとき、同じ刻み幅でまとめることができます。上で見たように、範囲があるので、これをまとめると階段関数になります。階段が上下する点も少ないので、これである程度速くなります。

最後に、刻み幅は例えば、4と6だったら、共通部分は12、すなわち最小公倍数になります。これが意外と遅い。なので、分割統治法の最初の分割で互いに共通因子が無いようにします。例えば、1〜13なら、7,11,13とそれ以外に分けます。そうすると、最後で最小公倍数の代わりに掛け算を使うことができ、さらにほかの高速化もできます。

結果はこうです。

F(10^12) = 999999494802129045868607 0.375sec
F(10^13) = 99999984077613685612998021 0.750sec
F(10^14) = 9999999497624726793960874036 0.609sec
F(10^15) = 999999984137697761708961227516 1.484sec
F(10^16) = 99999999498907434707071928610549 3.547sec
F(10^17) = 9999999984165144778636197325836865 3.672sec

続きを読む