2010-09-01から1ヶ月間の記事一覧

母関数

母関数は数え上げや確率の問題で使います。Project Eulerではときどき使えるのでおぼえましょう。最近ではProblem 286で使いました。例えばこんな問題で使えます。 N個のブロックが横一列に並んでいます。赤・青・緑・黄の4色のペンキがあり、これらで各ブロ…

product(2)

C++

Pythonではジェネレータでこういうことができます。 def gen(): for n in range(3): for m in range(n + 1, 4): yield (n, m) (0, 1) (0, 2) (0, 3) (1, 2) (1, 3) (2, 3)直積ではなく、mを出すiterableがnに依存しています。これを実現するにはどうすればよ…

Project Euler 303(2)

http://projecteuler.net/index.php?section=problems&id=303 この問題はもう200人以上解けているからいいだろう。 nが9の連続(あるいはその倍数)になっているときにf(n)が大きくなることは実験してみるとすぐにわかる。そこで、例えば99で割れる数を出す…

product(1)

C++

2つのiterableの直積です。タプルを返します。 template<typename T, typename U> class cProduct : public cIterable<tuple<T,U>> { shared_ptr<cIterable<T>> gen1; shared_ptr<cIterable<U>> gen2; vector<U> v; typename vector<U>::const_iterator p; int mode; public: cProduct(shared_ptr<cIterable<T>> g1, shared_ptr<cIterable<U>…</citerable<u></citerable<t></u></u></citerable<u></citerable<t></tuple<t,u></typename>

Project Euler 303

http://projecteuler.net/index.php?section=problems&id=303 やっと問題見た。 100までは割と簡単に出たけど、10000は厳しそう。 うーん、できそうだけど、メモリが足りない。 メモリ使わないように工夫して、できたと思ったんだけど、はねられた。 おかし…

iterate

C++

iterate(x, f)でx, f(x), f(f(x)), ...と出します。unfoldでも実現可能だけど、めんどうなので。 template<typename T, typename U> class cIterate : public cIterable<T> { T current; U func; bool first; public: cIterate(T x, U f) : current(x), func(f), first(true) { } bool e</t></typename>…

all,any

C++

allはすべてがtrueならtrueを、そうでなければfalseを返します。 anyはどれか一つがtrueならtrueを、そうでなければtrueを返します。 bool all(shared_ptr<cIterable<bool>> g) { while(g->exists_next()) { if(!g->value()) return false; } return true; } bool any(shared</citerable<bool>…

Priority Queue

プログラミングコンテストチャレンジブック作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本(ソフトカバー)購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見るまだ4割ほどし…

chain

C++

cIterableをつなげます。 template<typename T> class cChain : public cIterable<T> { shared_ptr<cIterable<T>> gen1; shared_ptr<cIterable<T>> gen2; bool first; public: cChain(shared_ptr<cIterable<T>> g1, shared_ptr<cIterable<T>> g2) : gen1(g1), gen2(g2), first(true) { } bool exists_next() { if(first) { if(!ge</citerable<t></citerable<t></citerable<t></citerable<t></t></typename>…

整数同士の除算

元ネタ http://python-history-jp.blogspot.com/2010/09/pythonc.html Pythonのこの挙動、知らなかった。 print -1 / 3 # -1 print -1 % 3 # 2 C++なら、 std::cout << -1 / 3 << std::endl; // 0 std::cout << -1 % 3 << std::endl; // -1 何度この挙動に悩…

cycle

C++

繰り返し値を出します。 template<typename T> class cCycle : public cIterable<T> { shared_ptr<cIterable<T>> gen; vector<T> v; typename vector<T>::const_iterator p; bool first; public: cCycle(shared_ptr<cIterable<T>> g) : gen(g), first(true) { } bool exists_next() { if(first) { if(gen->ex</citerable<t></t></t></citerable<t></t></typename>…

Project Euler 302(2)

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

Project Euler 302

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

slice

C++

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>…

zip

C++

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>…

dropwhile

C++

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>…

unique_ptr(2)

C++

#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

C++

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>…

permutations(2)

C++

ちょっと工夫してあまりコピーが発生しないように書き直しました。 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>…

Project Euler 301

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

階乗を求めるための下限(2)

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

Project Euler 300(2)

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とすれば必ず整数の割り算で正しい答えは出る、というのは見た…

permutations

C++

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

Project Euler 300

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

超特大ジャンボ足し算クロス

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

unfold(2)

C++

前回の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>…

unfold

C++

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>…