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

Project Euler 151から(1)

この問題は前回やったようにメモ化を使って簡単に解けますが、動的計画法(DP)ではどうでしょうか。DPの問題点はどの状態になるかどうかわからないところです。よく例に出されるフィボナッチ数列なら、n項をFnとして、F1 = F2 = 1として、F3から順に求めて…

Project Euler 308

http://projecteuler.net/index.php?section=problems&id=308 少し出遅れた。 英語が全然わからないんだけど。 10分経ったらわかってきた。 2のべきなんか出てこないと思ったら、打ち間違えていただけだった。 2の83乗まで出てきたが。 解ける気がまったくし…

メモ化

メモ化(memoize)は、Project Eulerで何問かに1問必ず使う手法なので、絶対に覚えましょう。 Project EulerのProblem 151を考えます。意味が分かりにくい問題ですが、分かれば簡単です。まず最初にA1の紙が1枚封筒に入った状態を考えます。この状態を (1, 0…

Project Euler 306(3)

http://projecteuler.net/index.php?section=problems&id=306 この問題はまともに解くとDPで2つ前の項を使うのでパッと見は並列化できないように思えるが、少し工夫すればほぼ並列化できる。 4分20秒くらいだったのが、4コアで並列化して69秒になった。4分切…

最大の三角形を探す(5)

さて、元の問題をもう一度。 n本の棒があります。棒iの長さはaiです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。 プログラミング…

Project Euler 307

http://projecteuler.net/index.php?section=problems&id=307 どうしてもオーバーフローする 間違えていただけだった。ムダに時間を費やした。5着。 これ、すぐに誕生日の問題と同じだと気づいたのに。 まあ、食事の時間の前に片がついたのはよかった。 フォ…

最大の三角形を探す(4)

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

最大の三角形を探す(3)

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

最大の三角形を探す(2)

まず、しらみつぶしに調べてみましょう。といってもこんな風にやるのは無理なので、数を小さくします。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>…

Project Euler 306(2)

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

Project Euler 306

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

最大の三角形を探す(1)

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

実は手ごわいuncertaintiesモジュール

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

partial_sort

STL

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

Project Euler 305

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

回文数

C++

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

ゲームの必勝法

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

itertools.h

C++

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

ダイクストラ法

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

reversed

C++

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

Project Euler 304

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で生成する…

iter

C++

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

list

C++

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>