Project Euler
220 Heighway Dragon Problem 220 - Project Euler ドラゴン曲線といえば，有名なフラクタル．
219 Skew-cost coding Problem 219 - Project Euler 語頭符号と聞くと，ハフマン符号を思いつきますが， Huffman coding - Wikipedia 今回は，単純な符号長ではなく重み付きの符号長になっているのが違うところ． 符号化が問題になっているわけではないので…
218 Perfect right-angled triangles Problem 218 - Project Euler ようするに，原始ピタゴラス数に関する問題．
217 Balanced Numbers Problem 217 - Project Euler 探索範囲が広いので、全探索は無理。 また、個数ではなく、和が必要。 さて、どうDPを構成するか…
212 Combined Volume of Cuboids Problem 212 - Project Euler はじめは平面走査で行こうと思ったが…
216 Investigating the primality of numbers of the form 2*n^2-1 http://projecteuler.net/index.php?section=problems&id=216 ミラー・ラビンを使うのも、ひとつの方法でしょう。 しかし、それは問題の主旨に反するような気もする。 では、どうするか…
211 Divisor Square Sum Problem 211 - Project Euler 約数関係の問題は、たいてい、因数分解・除算などは効率が良くないので、使えることが少ない。 では、どうするか？
210 Obtuse Angled Triangles Problem 210 - Project Euler 格子点を数えるタイプの問題。 はじめ、問題をよく読まずに、正方形でなく、円の中の格子点を数えるのかと思った。 あとで、実は正方形だと気がついたが…
208 Robot Walks Problem 208 - Project Euler 問題のサイズなどから、動的計画法を使うのが良さそうではあるが、 気になるのは、何を状態とするか、ということ。
209 Circular Logic Problem 209 - Project Euler 関数 が どのような振舞をするかを考えれば良いような、気がするが…
206 Concealed Square Problem 206 - Project Euler 全探索しては身も蓋もないので、すこし工夫しましょう。という問題なんでしょうか？
205 Dice Game Problem 206 - Project Euler サイコロ遊び。
203 Squarefree Binomial Coefficients Problem 203 - Project Euler とりあえず、適当につくったら、そのまま解けてしまった。
202 Laserbeam Problem 202 - Project Euler 鏡の反射と聞いたら、三角形をたくさん並べてみたくなるのが、人の常。 そうすると、格子点がいくつかできるが、Cが反射してできたの点が規則的に並んでいるのが分かる。 要は、ある数と互いに素な数をある範囲で…
Problem 207 - Project Euler この問題はハマッタ。
201 Subsets with a unique sum Problem 201 - Project Euler 特別な集合だから、賢い解法があるのかとも思ったけど、 思いつかなかった。 こういう、問題はDPがほとんど。 問題はどうDPを構成するか。
200 Find the 200th prime-proof sqube containing the contiguous sub-string "200" Problem 200 - Project Euler 2、5が含まれていれば、prime-proofだということはすぐに分かる。 つまり、prime-proofの十分条件。気になるのは必要条件だが…
Problem 198 - Project Euler ちょっとしたミスでした．基本は途中経過で述べたこと． 以下コード．
199 Iterative Circle Packing Problem 199 - Project Euler Apollonian gasket っていうらしいです．フラクタル． Apollonian gasket - Wikipedia 問題は3つの円に接する円の半径を求めることだと思いますが…
Problem 198 - Project Euler まだ，解けていませんが，考えをまとめるために，メモ． (つまり，間違ったことを書いている可能性アリ) How many ambiguous numbers x = p/q, 0 x 1/100, are there whose denominator q does not exceed 10^8? まず目につくの…
197 Investigating the behaviour of a recursively defined sequence Problem 197 - Project Euler どうせ循環するのだろうと思い，はじめの1000項をgnuplotでプロット． 実はすぐに，収束していた． 収束のしかたが単純． f :: Double -> Double f x = let…
196 Prime triplets Problem 196 - Project Euler 素数関係の問題． code (haskell) とりあえず，ナイーブなもの． 実行時間はisPrime'の効率に依存． つまり，遅い． 1000秒もかかった． import Data.Maybe (mapMaybe) import Number (isPrime') t :: (Inte…
Inscribed circles of triangles with one angle of 60 degrees Problem 195 - Project Euler 前にやった問題で似たようなものがあった(たしか，トリチェリの三角形だった気がする)． はじめは，外接円だと思っていた． import Control.Monad (guard) p195 r…
Problem 193 - Project Euler 平方数で割り切れない2^50以下の数を数える． メビウス関数と包除原理を利用． import Control.Monad.ST (ST,runST) import Control.Monad (when) import Data.Array.ST (STUArray,newArray,readArray,writeArray) p193 :: Inte…
Coloured Configurations Problem 194 - Project Euler 困難は分割せよ．ということで，それぞれのユニットごとの塗り分けパターンを考えてみた． 結果． choose :: (Integral a) => a -> a -> a choose n r = div (product [n-r+1..n]) $ product [1..r] p1…
Problem 192 - Project Euler 最良近似有理数とでも呼ぶのでしょうか． 探索範囲と√nの形から，どうやら連分数と関係がありそうだ，と思っていたら， Continued fraction - Wikipedia あとはSemiconvergentsの単調性を利用． import Data.List ((\\)) import…
Problem 188 - Project Euler これは前に解いた． import Number (factors) import Data.List (group) phi :: Integer -> Integer phi = product.map f.group.factors where f ps@(p:_) = let n = length ps in p^(n-1)*(p-1) towerMod :: Integral a => Int…
Problem 190 - Project Euler ラグランジュの未定乗数法を使うだけ． import Data.Ratio ((%)) p :: (Integral a, Integral b) => a -> b p m = floor.product $ [(2*n % (m+1))^n | n <- [1..m]] p190 :: (Integral a, Integral b) => a -> b p190 m = sum.…
Problem 189 - Project Euler まぁ，DPですな． import Data.List (delete,nub) import Data.Maybe (mapMaybe) import Data.Map (fromListWith,toList) import Control.Arrow ((***)) data Color = R | G | B deriving (Eq,Ord,Show) normal :: [Color] -> […
http://projecteuler.net/index.php?section=problems&id=187 まぁ，関数型ではやりにくい． とりあえず，javaで． 非常にシンプルな，ふるいを使ったアルゴリズム． import java.util.Arrays; public class P187{ public static void main(String[] args){ …
