Project Euler
Problem 289 - Project Eulerある特殊なグラフの交差のないオイラー閉路の数を求める問題。 一般の無効グラフにおけるオイラー閉路の数を求めるのは難しいらしいです。この問題、正解者が少ないけど、理論的にはそんなに難しくないと思う。 ただ、実装が面倒…
Problem 288 - Project Euler特に難しくない、というか簡単な部類だと思う。 ただ、第0項から第n項までには、n項しかない、と思ってハマった。 運が良いのか、悪いのか、勘違いしたままでも、テストケースは正しい答えを返す。# この手のミスが多い気がする…
Problem 279 - Project Euler似た問題を昔やったような．なぜか愚直な方法と賢い方法の答えがあわずに苦戦した． どうやってもあわない． 実は愚直な方法が間違っていたという，情けないオチ．Haskellで約2秒． C++で約0.3秒． こんなもん？
Problem 278 - Project Euler面白い． 視点を変えると世界が変わる．
http://projecteuler.net/index.php?section=problems&id=273 実は本筋とはあまり，関係がないのだが，4n+1型の素数の平方和分解は前に実装したことがある． http://d.hatena.ne.jp/jeneshicc/20081221/1229835537 それもあって今回の問題はパッとやってピッ…
Problem 271 - Project Euler Problem 272 - Project Euler 誤解を恐れずに，問題の雰囲気を紹介すると．「n が与えられて，x^3 = 1 (mod n) となる x は？」です． ある性質が鍵だと思う． 271のほうは多分簡単． Haskellでも実行は一瞬． 272はそんなに難…
Problem 270 - Project Euler何通りの分割の仕方があるか？系の問題． 冷静に場合分けなどを考えていけば，解ける． そんなに難しくないはずだった． ただ，ずっとN=29だと思って，答えが合わずに悩んでいた．なんというアホ． やはり，MemoTrieは便利だ．
Problem 269 - Project Euler そこまで難しくないが，なかなか面白い． アルゴリズムが結構気に入った．
Problem 268 - Project Euler最近は比較的簡単なものが多い？
http://projecteuler.net/index.php?section=problems&id=267 単純な計算ミスを多数して，どうしようもなかった． 問題自体は簡単． メモ import Text.Printf して printf "%.12f\n" pi とすると有効数字12桁で表示してくれる．
Problem 265 - Project Euler これは簡単． だって，N=5だし． 計算量とか全然考慮せずに実装したが，実行は一瞬． ただ，Nが大きい場合，どうやって効率的に解くのかな？# eulerに現を抜かしている暇はないはずだが…
Problem 264 - Project Euler いつもの整数問題． とりあえず，愚直な方法をHaskellで実装して， 遅くて，遅くて，しかたなったので， C++ならいけるはず（この計算量なら）と思い， C++で実装したら，約60倍速くなった．びっくり．しかし，愚直な方法なので…
Problem 263 - Project Euler いつもどうりの整数の問題． 探索範囲の上限がよく分からないことが，けっこう怖い． しかも，普通に考えると，素因数分解と素数判定が必要だから，計算量が大きくなりそうな予感．とりあえず，brute forceしたら，時間かかった…
Problem 262 - Project Euler 最短距離を求める問題． しかし，離散的な問題ではなく，連続的な問題． 山の高さを表す関数が与えられて，最小高度で移動したときの最短距離を求める． 詳細は，project eulerのサイトで．高さを表す関数が簡単な形ではないの…
Problem 261 - Project Eulerん？運良く解けた？ 計算スピードのために，多分正しいショートカットを使っているから，良く分からない． はじめは N=10^11だと思ってました．しかし，また，フォーラムにマジカルな（理解できない）解法が載っていた．うーん．…
Problem 260 - Project Euler 21ゲーム（交互に数字を言って，21を言ったら負け）みたいなノリ．メモリが沢山あるマシンなら，簡単（比較的簡単な全探索で解ける）だと思う．最初は，loosing configurationの条件が，バシッと書けると思い，小さい数字でいろ…
Problem 259 - Project Euler 問題読んで，理解して，テケトーに（計算量を全然見積らず）実装したら，答えでた． たぶん，簡単な部類．最近，ちょっと難しい問題が多めだったから，息抜きなんですかね．まぁ，計算式を二分木で表現するのは良くあることで（…
けっこう，（といっても，4，5日前だが）に解いた．問題文は簡単．g(k) = 1 if 0 g(k) = g(k-2000) + g(k-1999) if 2000 find g(10^18) (mod 20092010)普通のFibonacciだったら，簡単ですが． そう簡単にはいかない．まぁ，それが今回の問題ですか． Haskell…
Problem 257 - Project Euler 三角形の問題なんだが，それを忘れてしまうほど， 三角形の存在が薄い（三角形という条件は重要）． こういう問題は前にもあったような，なかったような．取り敢えず，解いたが， 理論的な保証が無いので，そこらへん，もうチョ…
ある規則性を観察できれば，おしまい． もう，解けたも同然である． （と思っていた．今，考えなおすと，たんなる必要十分条件を求めただけで，それが偶然十分必要条件でもあった．ラッキー）しかし，アホなコーディングしたせいで，時間がかかった． どうに…
畳がでてくるので，畳好きの日本人としては，紹介しないわけにはいかない．（問題の雰囲気を伝えることを目標にする．詳しくは Problem 256 - Project Eulerで）どんな問題かというと… 縦がa,横がbの長方形の部屋（a （画像はhttp://projecteuler.net/index.…
Problem 255 - Project Euler解いた．前2問に比べると簡単だと思う（もう内容忘れかけているが）．はじめにHaskellで解いたら，実行時間は3分ぐらいだった． 再帰を使おうとしたら，stack space overflow． seq入れてみたり，!入れてみたりして，stack space…
取り敢えず，解いた． しかし，少し遅い．約20秒 (Core 2 Duo E8500).もうすこし工夫して下限を求めるか， 探索方法を工夫するか， の二択なのか？ 追記 #1 ad hoc な工夫をして，約3秒になった． しかし，もう少し綺麗な改良の方法はないのか？ 追記 #2 C++…
Problem 253 - Project Euler 取り敢えず，解いたが，フォーラムのシンプルかつ高速な解法が理解できない… それにしてもMemoTrieは強力だ．お手軽，メモ化．ほとんどコードを変えることなくメモ化できる． やはり，高階関数は便利． # import MemoTrie とし…
Haskellが遅かった． 1分以上． そこで，単純な全探索を少し工夫して，しかも，C++で実装したら， 5秒未満になった． #include <iostream> #include <vector> #include <boost/rational.hpp> #include <boost/foreach.hpp> #define FOREACH BOOST_FOREACH using namespace std; typedef boost::rational<int> rat; static co</int></boost/foreach.hpp></boost/rational.hpp></vector></iostream>…
252 Convex Holes Problem 252 - Project Euler 計算幾何の問題． 二次元平面上に点集合が与えられる． 最大空凸包とでもいうのでしょうか？ 凸包であって，内部に他の点を含まないもの のうちの最大面積を求める問題． さて，どこから手を付ければ良いのや…
251 Cardano Triplets Problem 251 - Project Euler ある条件を満たす，三つ組の整数を探すもんだい． 条件に三乗根があり，しかも，その中に二乗根まであるので，見た瞬間は，ぎょっとしますが…
レベルが上がって，球になった． ところで，次のレベルはどうなるんでしょう？
250 250250 Problem 250 - Project Euler 前の問題（249）と似ているが…
249 Prime Subset Sums Problem 249 - Project Euler 部分和問題はNP困難で，難しそうですが…
