http://projecteuler.net/index.php?section=problems&id=302 コード書いている時間がないので、昨日のコードのままで2時間弱走らせて答えを得た。ただ、3時間以上かかると思っていたので今日に回したが、これなら昨日中に答え出てたなあ。

http://projecteuler.net/index.php?section=problems&id=302 素直に書いてやっと104が出たと思ったら、108が間違っている。 コメントにサイトが落ちているとあったので、リロードしてみたら、確かにアクセスできなくなっていた。でかけている間に、問題文を…

zipを使うと簡単にスライシングのコードが書けます。 template<typename T> class cSlice : public cIterable<T> { shared_ptr<cIterable<tuple<int,T>>> gen; int current; int end; int delta; bool last; shared_ptr<cIterable<int>> counter; public: cSlice(shared_ptr<cIterable<T>> g, int n) : current(0), end(n), delt</citerable<t></citerable<int></citerable<tuple<int,t></t></typename>…

2つのIterableが並行に（tupleにして）値を出せるようにします。長さが違う場合は短いほうにあわせます。 #include <tuple> #include "itertools.h" using namespace std; using namespace itertools; template<typename T, typename U> class cZip : public cIterable<tuple<T,U>> { shared_ptr<cIterable<T>> gen1;</citerable<t></tuple<t,u></typename></tuple>…

takewhileと似ていますが、実のところあまり使いません。 叙述関数がtrueの間は値を出しません。 template<typename T, typename U> class cDropWhile : public cIterable<T> { U pred; std::shared_ptr<cIterable<T>> gen; bool first; public: cDropWhile(U p, std::shared_ptr<cIterable<T>> g) : pred(p), gen(</citerable<t></citerable<t></t></typename>…

#include <iostream> #include <memory> class C { int n; public: C(int m) : n(m) { } ~C() { std::cerr << "C:~C" << std::endl; } int get() const { return n; } }; int main() { auto p = std::unique_ptr<C>(new C(1)); auto q = std::move(p); auto r = std::unique_ptr<C>(n</c></c></memory></iostream>…

unique_ptrの使い方を勉強してみました。 #include <iostream> #include <memory> class C { int n; public: C(int m) : n(m) { } ~C() { std::cerr << "C:~C" << std::endl; } int get() const { return n; } }; int main() { auto p = std::unique_ptr<C>(new C(1)); std::cout <</c></memory></iostream>…

ちょっと工夫してあまりコピーが発生しないように書き直しました。 template<typename T> class cPermutations : public cIterable<vector<T>> { typedef typename vector<T>::iterator IT; template<typename T> class cPerm { typedef shared_ptr<cPerm<T>> PTR; IT begin; IT end; PTR g; const int n; i</cperm<t></typename></t></vector<t></typename>…

http://projecteuler.net/index.php?section=problems&id=301 6時前に目が覚めて問題文を見る。長い。読もうとするが、眠くてなかなか進まない。問題文を読み終えて、特になにも思いつかないので、もっとも原始的にコーディングしてみる。 def X(stones): if…

nk / nCk < k! + 1 となるnを、明示的になるべく小さくなるように求めようという話でした。このnをNとします。 逆数を取って、 P ≡ 1...(1 - (k - 1) / N) > 1 / (1 + 1 / k!) さて、こういうのはlogを取って積分で近似するのが定番です。 log 1 + ... + log…

http://projecteuler.net/index.php?section=problems&id=300 やれやれ。結局、C++で組んで無理矢理答えを出した。

ネタ元 http://www.kmonos.net/wlog/113.html#_2256100904階乗を求めるのに、 k! = limn → ∞ nk / nCk という方法がある。これはどこかで見たことがあるような気がする。ただ、n = (k + 1)k + 2とすれば必ず整数の割り算で正しい答えは出る、というのは見た…

順列を次々に出します。 例えば、[ 1, 2, 3 ]というリストがあったとして2要素の順列を出すと、 [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]となります。このpermutationsはPythonでは簡単に書けます（本当はライブラリにあるのでこれ…

http://projecteuler.net/index.php?section=problems&id=300 もうすぐ問題が出る。2ヶ月ぶりなので、たぶん問題を理解するだけでも時間がかかるだろう。今日は時間がないので、すぐにわからなかったら風呂に逃げる予定。 なかなか繋がらない。タイトルだけ…

足し算クロスというのは1〜9の数字をマスにいれて和を指定した数にするパズルである。その列で同じ数字を使ってはいけない。例えば、 ３ ３ □ ⇒ ２ ４□□ ４１３となる。 このパズルの特徴は、ナンプレ（数独）とちがって数の大小が重要なので、数の特徴が見…

前回のunfoldは無限列しか出しません。それをtakewhile止めています。しかし、例えば整数を10進数に分解することを考えます。10で割った余りを出していくと、 shared_ptr<cIterable<int>> digits(int n) { auto f = [] (int n) { return pair<int,int>(n % 10, n / 10); }; return un</int,int></citerable<int>…

Haskellなどにあるunfoldは、reduceの逆で初期値からリストを作っていきます。 f(状態0) → (値1, 状態1) → 値1 f(状態1) → (値2, 状態2) → 値2 という具合に値を出していきます。 reduceの逆なのにunfoldなのはあまり気にしない方向で。 template<typename T, typename U, typename V> class cUnf</typename>…

フィボナッチ数列を適当に作ります。 class cFib : public cIterable<int> { int a; int b; public: cFib() : a(1), b(1) { } bool exists_next() { int tmp = b; b += a; a = tmp; return true; } int value() const { return a; } }; shared_ptr<cIterable<int>> fib() { retur</citerable<int></int>…

Pythonのcountは指定した数から順に整数を出していきます。ここでは、引数で公差も指定できるようにしました。 class cCount : public cIterable<int> { int current; int delta; public: cCount(int s, int d) : current(s - d), delta(d) { } bool exists_next(</int>…

takewhileは、叙述関数がtrueである限り値があれば出し続けます。 template<typename T, typename U> class cTakeWhile : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cTakeWhile(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { } bool exists_next() { return gen->exists_next</citerable<t></citerable<t></t></typename>…

失敗した話。 #include <string> int main() { try { throw(""); } catch(std::string e) { ; } } こんなコードで例外を捕えられませんでした。実際にはこれほど単純なコードではなかったのですが。無意識のうちにこういうコードから連想していたようです。 #include <string></string></string>…

リストに対して写像を施して別のリストを作ります。 template<typename T, typename U, typename V> class cMap : public cIterable<T> { U func; shared_ptr<cIterable<V>> gen; public: cMap(U f, shared_ptr<cIterable<V>> g) : func(f), gen(g) { } bool exists_next() { return gen->exists_next(); } T value() const { r</citerable<v></citerable<v></t></typename>…

sumを作りたいのですが、その前にPythonでreduceと言ったり、Haskellでfoldと言ったりするものを作ります。リストなどに関数を次々に適用してスカラー値にするものです。(1, 2, 3)にf(x, y) = 10x + yを適用していくと、初期値を0として、 10 * 0 + 1 -> 1 1…

Pythonのifilterを作ります。叙述関数を適用してtrueになる要素だけ出します。 以下は、3の倍数だけ出力するコードです。 template<typename T, typename U> class cFilter : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cFilter(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { </citerable<t></citerable<t></t></typename>…

Pythonのitertoolsを使ったような書き方がC++でもできるようにライブラリを作っていきます。具体的には、例えば、1から10の和を求めるときにこう書けるようにします。 cout << sum(range(1, 11)) << endl; Pythonのxrangeやtakewhileをクラスを使って実現し…

http://projecteuler.net/index.php?section=problems&id=150 Pythonってこういう書き方ができたんですね。知らなかった。 for (i, j), s in izip(gen_index(N), gen_pseudo_random()): これとの連想で、ラムダでもこういう書き方ができます。 lambda (i, j)…

http://projecteuler.net/index.php?section=problems&id=149 よく考えたら、これって左から順に考えたほうが簡単ですね。そうすると、全体の和、最大の和、右端を含む最大の和の3つを考えれば済みます。こうするとコードがすっきりした上、46秒でした。再帰…

http://projecteuler.net/index.php?section=problems&id=149 整数の列に対して部分列の和の最大を求める問題です。 列の長さをnとすると、部分列の決め方でO(n2)、和を取ってO(n3)の計算量になります。和は重複を避けるとO(n2)となります。しかし、これでも…

http://projecteuler.net/index.php?section=problems&id=148 数学的にはよくわかりませんが、実際に数えてみるとわかります。1行で7で割れない数えてみると、明らかな法則性が見えてきます。7進数で考えるとわかりやすいでしょう。その和は、7のべき乗まで…

http://projecteuler.net/index.php?section=problems&id=147 水平の長方形の個数の計算は電卓レベルなので、斜めの長方形について考えます。 この問題はよく考えると、同じ長方形がいくつあるかという数え方と、点を固定してそれを頂点とする長方形はいくつ…