2012-12-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時間くらいかけただろうか。明日以降もうちょっとなんとかする。