2012-01-01から1年間の記事一覧

#include <iostream> #include <vector> #include <sstream> #include <windows.h> #pragma comment(lib, "winmm.lib") using namespace std; typedef long long ll; typedef vector<ll> vec; const ll INF = (ll)1e18; template<typename T> ostream& operator <<(ostream& os, vector<T>& v) { if(!v.empty()) { os <<</t></typename></ll></windows.h></sstream></vector></iostream>…

Project Euler 407(2)

http://projecteuler.net/index.php?section=problems&id=407いつものように逆から解いてみたが、6分が2分40秒になった。元がO(N(logN)^2)だったのをO(NlogN)にしたつもりだったが、どうもO(N(logN)^2)のままっぽい。

Project Euler 407

http://projecteuler.net/index.php?section=problems&id=40722着。 久しぶりに1時間以内に解けた。 ただし、6分もかかった。nについて一つずつ求めた。計算量はよくわからない。 速くするには全体で解かないといけないと思う。

Project Euler 406

http://projecteuler.net/index.php?section=problems&id=40671着。 月曜の帰りに解法に気がついたが、色々勘違いしてうまく組めなかった。組めたと思ったら、答えが合わない。精度がやや厳しそうなので、積算で誤差が積み重ならないような計算法にした。そ…

分割数

分割数というのは、例えば5を自然数で分割することを考えます。同じ数を何度も使ってもよいですが、順序違いは区別しません。そうすると、 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1の7通りあります。これを p(5)…

10^e乗の計算法

昨日のProblem 405に関連するが解くのには必要のない情報。 10e乗の剰余は、Pythonにはpow関数が用意されて簡単に計算できます。例えば、3の1010乗の123456789の剰余は、 pow(3, 10 ** 10, 123456789)で求められます。しかし、指数が大きくなってくると段々…

Project Euler 405

http://projecteuler.net/index.php?section=problems&id=40551着。 これは100番台によくある問題に毛が生えたもの。違うのは100番台はN = 40とかだが、今回は10の10^{18}乗だということ。しかし、100番台もいつも大きな数にも対応できるように書いていたの…

Project Euler 404(2)

http://projecteuler.net/index.php?section=problems&id=404小手先で高速化して3分弱になった。しかし、これ以上速くするにはいつものあの手を使わなければならず、たぶんかなりめんどう。

Project Euler 404

http://projecteuler.net/index.php?section=problems&id=40444着。 今回もひどいコードを書いた。並列化しやすいので最大4コア使って、全部で3時間くらいかけただろうか。明日以降もうちょっとなんとかする。

Project Euler 403

http://projecteuler.net/index.php?section=problems&id=40332着。 本当にひどかった。O(N)にしたまではまだよかったが、そのあとは値の傾向を見て、いつものアレを使うのだが、境界を求めるのが面倒で二分探索して。最後はint_sqrtを自作した。

Project Euler 402

http://projecteuler.net/index.php?section=problems&id=40249着。0.2秒。 2つ問題を組み合わせたような感じできつかった。 最後はつい最近使ったばかりのアレを使って仕上げた。

Project Euler 401

http://projecteuler.net/index.php?section=problems&id=40185着。よく考えたらいつものやつだった。Project Eulerで頻出のテクニック。 でも72秒もかかっている。

Project Euler 400(2)

http://projecteuler.net/index.php?section=problems&id=400O(N2)になるコードをPythonで書いたら64秒になった。

Project Euler 169(2)

Problem 169 コードはフォーラムに。

Project Euler 400

http://projecteuler.net/index.php?section=problems&id=40072着。C++で書いて12秒。 Pythonで再帰が深すぎ&メモリ食いすぎのためC++にした。その後Pythonでも再帰使わずメモリも食わない方法を考えて組んだら650秒。もうちょっと速くならんのか。実験して…

Project Euler 399

http://projecteuler.net/index.php?section=problems&id=399119着。46秒。 ずっと答えが合わなかったが、1個後ろを見ていただけだった。

Project Euler 398

http://projecteuler.net/index.php?section=problems&id=39848着。7秒。 誰でも思いつくような方向は絶対違うなと思って別の方向を考えていたが、ちっとも解法が現れてきそうにない。次の日にそういえば捨てた方向があるなと思って帰りに考えたら間に合いそ…

Project Euler 397

http://projecteuler.net/index.php?section=problems&id=39734着。20分くらいかかっている。 日曜の夜にはだいたいできてたんだけど、そっからのデバッグになかなか時間が取れなくて。だいたい電車の中で手計算していた。F(3, 10)の正しい答えが出たらあと…

Project Euler 396(2)

http://projecteuler.net/index.php?section=problems&id=396この問題には実は微妙なところがある。 それをフォーラムに書いた。

Project Euler 396

http://projecteuler.net/index.php?section=problems&id=39629着。 手計算すればだいたいわかる。 G(8)以降は爆発して剰余の計算をしなければならないが、意外と簡単である。

Project Euler 361(2)

http://projecteuler.net/index.php?section=problems&id=361あれからいろいろ考えて、なんとかAnの計算量をO(log n)にしたかったのだが、結局断念した。 それでもだいぶ速くなった。1018まで 0.06s 1050まで 0.65s 10100まで 0.41s 10200まで3s 10400まで23s

Project Euler 395

http://projecteuler.net/index.php?section=problems&id=39525着。15ms。 ふつうに組んだら倍々ゲームになるので答えは出ない。PCを離れて考えてみたらすぐに思いついた。

ABC予想とProject Euler

数学の難問「ABC予想」、京大教授が解明かWikipediaを読んでもわからないと思う。ここのrという関数は、Project Euler Problem 127に書かれているradのことのようだ。この問題ではc 20まで求められているらしい。どうやって求めればよいのだろう。 [追記 …

Project Euler 394(2)

http://projecteuler.net/index.php?section=problems&id=394今朝考え直して、分割数Nとして計算量がO(N2)からO(N)になった。これでインチキしなくても20秒で収束した。

Project Euler 394

http://projecteuler.net/index.php?section=problems&id=394なかなか収束しないんだけど、加速法を2回使ったらなんか収束した。

Project Euler 289

未解決問題を解こうシリーズ第7弾。http://projecteuler.net/index.php?section=problems&id=289382着。 Problem 393とだいたい同じ。

Project Euler 393

http://projecteuler.net/index.php?section=problems&id=39371着。単なる実装ゲー。

Wilsonの定理の拡張

Problem 160に少し出てくるので考えてみました。Wilsonの定理は、 pが素数なら(p - 1) ! ≡ -1 です。これは、pを法とした既約剰余類群の元を全て掛け合わせると-1となる、とも言えます。その積をP(p)と書くことにします。例えばp = 7として P(7) = 1 * 2 * 3…

Project Euler 361

未解決問題を解こうシリーズ第6弾。http://projecteuler.net/index.php?section=problems&id=361123着。20ms程度。今まで最も解かれていない問題。現在正答者200人以下の問題は10問らしい。それだけ難解にしてかつ華麗な問題。なんとか再帰に持ち込む。しか…

Project Euler 392

http://projecteuler.net/index.php?section=problems&id=39274着。何を間違えているのかと思ったら、符号だった。簡単な問題なのに。