次の図のように考えるとうまくいきます。赤い部分が長いほうから見て最長の同じ長さの棒があるところで、この長さをkとします。長さが、100, 60, 40, 20, 20, 20, 10, 5, 5とすればkは20です。なぜこうするとよいのかというと、同じ長さの棒があると、そこで…

なんとかDPかメモ化ができないでしょうか。 例えば、棒を長い順に並べなおして、最初が10、9、8だったとすると、これ以降がどうであれ1回目で三角形になることがわかりますね。だから、この場合の数を数えればしらみつぶしよりかなり効率的に数えることがで…

まず、しらみつぶしに調べてみましょう。といってもこんな風にやるのは無理なので、数を小さくします。N = 10、M = 7としてみました。 #include <iostream> #include <algorithm> #include <functional> const int N = 10; const int M = 7; int c[M]; bool is_trianble(int *a) { return a[0] </functional></algorithm></iostream>…

http://projecteuler.net/index.php?section=problems&id=306 結局、N=106としてGrundy数をNまで求めればいいんだけど、O(N2)なのでなんともならなくて、昨日の段階では20時間以上かかると見込んでいた。でも、職場のPCなら8時間もあれば終わるんじゃないか…

http://projecteuler.net/index.php?section=problems&id=306 長い文が来た。5分で理解したけど、正しく理解したか不安。 やっと50が出たけど、よくわからないなあ。 10000でも50秒かかる。

n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。 プログラミングコンテストチャレンジブック …

元ネタ 曖昧な数値を曖昧なまま計算できるPythonのモジュール uncertainties これを読んだときはあまりよくわからなかったけど、インストールしていざ使ってみると、これはそんなに簡単なものではないようです。 from uncertainties import ufloat from unce…

std::partial_sortは、先頭から決められた数だけソートします。例えば、 #include <iostream> #include <algorithm> int main() { int a[] = { 7, 2, 5, 1, 6, 8, 3, 9, 4 }; const int size = sizeof(a) / sizeof(a[0]); std::partial_sort(a, a + 4, a + size); for(int i = 0; </algorithm></iostream>…

マージ法（Merge algorithm）は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。 原理は非常に簡単です。例えば次のような列があったとして、 2 4 6 8 ... 3 6 9 12 ... まず、両方の列の先頭を比較します。小さいほうの2を取…

http://projecteuler.net/index.php?section=problems&id=305 またなにやら大変そうな問題が。 f(5)すら正しく出ない。 1個間違えていただけだった。でも、f(12)が間違っている。 これもちょっと間違っていただけだった。 f(7780)がすぐに出ないようだと話に…

回文数とは前から読んでも後ろから読んでも同じ自然数、例えば13231などのことで、なぜかよくProject Eulerで出てきます。 回文数は再帰的に生成することができます。例えば、131という回文数があれば、これを10倍して10001の倍数を足すことで、11311,21312,…

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

今まで作ったcIterable関係をここにまとめておきます。予告なく修正されることがあります。

プログラミングコンテストチャレンジブックにダイクストラ法（Dijkstra's algorithm）の説明が載っていた。Wikipediaに書いてあった説明は意味が分からなかったが、これはわかりやすい。 これは、Project Euler Problem 83を解くときに思いついた方法そのも…

vectorを逆順に出します。 template<typename T> class cReversed : public cIterable<T> { const vector<T> v; typename vector<T>::const_reverse_iterator p; bool first; public: cReversed(const vector<T>& w) : v(w), first(true) { } bool exists_next() { if(first) { first</t></t></t></t></typename>…

http://projecteuler.net/index.php?section=problems&id=304 解ける気がしない。せっかく久しぶりにスタンバイできたのに。超強引に書いたら解けた。4分半。あとで短くなるように工夫しよう。フォーラムでは5番乗りだったが、解答は4番。4秒差か。工夫して…

フィボナッチ数列Fnは次のように定義されます。 F1 = 1 F2 = 1 Fn+2 = Fn+1 + Fn F2 = 2とする流儀もあるようです。 フィボナッチ数列はいろいろなところに出てくるためか、Project Eulerでもしばしば取り上げられます。フィボナッチ数列をPythonで生成する…

逆にvectorをiterableに変換します。 template<typename T> class cIter : public cIterable<T> { const vector<T> v; typename vector<T>::const_iterator current; bool first; public: cIter(const vector<T>& w) : v(w), first(true) { } bool exists_next() { if(first) { curre</t></t></t></t></typename>…

iterableをvectorに変換します。 template<typename T> vector<T> list(shared_ptr<cIterable<T>> g) { vector<T> v; while(g->exists_next()) v.push_back(g->value()); return v; } int main() { vector<int> v = list(range(3)); cout << v[0] << v[1] << v[2] << endl; } 012</int></t></citerable<t></t></typename>

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

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に依存しています。これを実現するにはどうすればよ…

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

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>

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

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はすべてが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>…

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

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 何度この挙動に悩…

繰り返し値を出します。 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>…