大方の予想を裏切り、見事完走できました。ほうとうおいしいです。

http://projecteuler.net/index.php?section=problems&id=117 そのままＤＰ。 import Data.Array.IArray measure n = mArr!n where mArr = listArray (0,n). map m $[0..n]::Array Int Integer m 0 = 1 m x = sum.map m'.zipWith (-) (repeat x) $ [1..4] m'…

前門と同じような考え方。むしろこっちのほうが簡単だと思う。 choose n r = div (product [n-r+1..n]) $ product [1..r] replace m n = sum[choose (n+t-t*m) t | t<-[1..div n m]] main = print.sum.zipWith replace [2,3,4] $ repeat 50

m=3のときred(5)black(2)red(3) (n=10)を次のように考える ■○○□○■(□)black(3)red(3)black(1)red(6)black(1) (n=14)ならば ○○○■□■○○○□(○)○：直前と同じ色（先頭ならblack） ■：red のはじまり（○ (3=m)個ぶん） □：black のはじまり (直前が red の終わり) 最…

http://projecteuler.net/index.php?section=problems&id=114 普通のDP import Data.Array.IArray measure n = mArr!n where mArr = listArray (0,n). map m $ [0..n]::Array Int Integer m n | n < 3 = 1 | n == 3 = 2 | n > 3 = sum [mArr!(n-m-1)| m<-0:[…

http://projecteuler.net/index.php?section=problems&id=113とりあえず、再帰式を考えて、DPにした。 しかし、かなりきれいな再帰式なので手計算できそうではある。が、いいや。 import Data.Array.IArray n = 100 mkArray :: (Ix i)=> (i -> Integer)-> (i…

http://projecteuler.net/index.php?section=problems&id=112 ナイーブな実装。遅くないので、よしとする。 map2 f xs = zipWith f xs $ tail xs descend, ascend :: Integer -> Bool descend = and.map2 (>=).show ascend = and.map2 (<=).show main = prin…

今日、イトーヨーカドーで靴下買ったら、 還元セール中で1割返ってきた。なんかちょっとうれしかった。 金額は100ぐらいなんだけど、大入袋に入って返ってきた。なんか、不況らしいけど、それと関係あるのかね？

http://projecteuler.net/index.php?section=problems&id=120簡単な計算（とするが、意外と時間がかかったのは内緒だ）で a:even -> a*(a-2) a:odd -> a*(a-1) が分かる。これが分かれば、後は簡単。 rMax a | even a = a*(a-2) | odd a = a*(a-1) main = pr…

http://projecteuler.net/index.php?section=problems&id=118いたって普通の解法だと思う。 import Data.List import Number permPrime :: [Char] -> Integer permPrime = genericLength.filter isPrime'.map read.permutations comb _ 0 = [[]] comb [] _ =…

ghc --make foo.hs -prof ./foo.exe +RTS -hc hp2ps foo.hp (fiber foo.ps)でなんか変なpsファイルができる。 みかたが良く分からないが、どうやらメモリ消費量のようなものを表しているようだ。参考： http://itpro.nikkeibp.co.jp/article/COLUMN/20070403…

http://projecteuler.net/index.php?section=problems&id=111普通の解法、同じ数が多い連続数から作って、素数かチェック。 import Number import Data.Char import Data.List toInt = read.map intToDigit :: [Int]->Integer repDigit (d+1) m (n+1) = [k:x…

http://projecteuler.net/index.php?section=problems&id=109とりあえず、再帰で書いて、DPになおそうと思った。 import Data.List score = sort$[1..20]++map (2*) [1..20]++map (3*) [1..20]++[25,50] double = map (2*) $ [1..20]++[25] finish0 n = map …

import Number import Data.List import Data.Maybe dscList lim max' | lim < 1 = [[]] | otherwise = [x:ys|x<-[1..max'],ys<-dscList (lim' x) x] where lim' y = lim / (2*(fromIntegral y)+1) p110 = dscList 7999999 60 decode = product.zipWith (^) …

http://projecteuler.net/index.php?section=problems&id=1081/a+1/b=1/nですが、b=n+b'と書き換えると n^2がb'で割り切れることが分かる。 従って、n^2が1999個の約数を持つ最小のnを探せばよい。 import Number import Data.List import Data.Maybe descen…

http://projecteuler.net/index.php?section=problems&id=106とりあえず問題文を理解するのにすごい時間がかかった。 なんで、n=4で25になるのか分からなかった。 とりあえず原因は 問題文がどこまでリストの要素が昇順である仮定をつかっているのか 明記し…

http://projecteuler.net/index.php?section=problems&id=105ちょっと考えたら、シンプルな解法に気がついた。 import Data.List monotone xs = all (f.sort$xs) [1..length xs `div` 2] where f ys n = (sum.take (n+1)) ys > (sum.take n.reverse) ys subs…

http://projecteuler.net/index.php?section=problems&id=104単純な解法 import Data.List fib = 0:1:zipWith (+) fib (tail fib) fibMod = map (flip mod (10^9))$0:1:zipWith (+) fibMod (tail fibMod) main = print.findIndex pandigit.zip fibMod $fib w…

http://projecteuler.net/index.php?section=problems&id=107どうみても最小木問題です。本当に(ryというわけで、今回はライブラリを使ってみた。 なんと、最小木を求める関数があるという充実ぶり。 import Data.List import Data.Array import Data.Graph.…

http://projecteuler.net/index.php?section=problems&id=102三角形の内部判定。 外積を使うと楽。かな。 import Data.List cross (x,y) (u,v) = x*v-y*u containO [x,y,z] = sameSign.map (uncurry cross)$[(x,y),(y,z),(z,x)] where sameSign xs = all (>0…

http://projecteuler.net/index.php?section=problems&id=101 少し頭を使った。 ただの階差数列は1次の多項式 ２階の階差数列は２次の多項式 ３階の階差数列は３次の多項式 n階の階差数列はn次の多項式 なので 階差の山を作って 各高さの右端の数字を全部足…

http://projecteuler.net/index.php?section=problems&id=218 ついに100問。 に対して とすると のpell equationに。 ところで、pell equationの解は最小の解から順に生成できるみたいだけど なんで？はじめの解をn乗しても解なのはわかるけど 間に解がない…

http://projecteuler.net/index.php?section=problems&id=99 そのまま、log使って比較。 import Data.List import Data.Ord logPow x y = y*(log $ x) main = do f<-readFile "base_exp.txt" let xs = map (read.g) . lines $ f ::[[Double]] ans = maximumB…

http://projecteuler.net/index.php?section=problems&id=103良く分からないから、とりあえず入力してみたらあっていた。 後でコードかこう。[追記] Problem 105を利用 import Data.List import Data.Ord monotone xs = all (f.sort$xs) [1..length xs `div`…

http://projecteuler.net/index.php?section=problems&id=98 アナグラムかつ平方数になる文字の組のうち、最大の平方数を求める。 先頭０だめを忘れていた。 import Data.List import Data.Function import qualified Data.Map as Map findAnagrams xs = map…

http://projecteuler.net/index.php?section=problems&id=96数独を解く問題。やっと速く動くようになった。 まったく、バグが大変だった。 import Data.List import Data.Char import Data.Ord import Data.Array.IArray import Control.Monad type Sudoku =…

資料作りが終わらない件について

powMod a n m | n < 3 = a^n `mod` m | otherwise = let (q,r) = divMod n 2 aq = powMod a q m in aq*aq*a^r `mod` m main = print $ (powMod 2 7830457 (10^10) * 28433 + 1) `mod` (10^10)

http://projecteuler.net/index.php?section=problems&id=94 また、pell equation. next (x,y) = (2*x+3*y,2*y+x) tolength x | (x+2) `mod` 3 == 0 = let a = (x+2) `div` 3 in 6*a-2 | (x-2) `mod` 3 == 0 = let a = (x-2) `div` 3 in 6*a+2 p094 = takeWh…

http://projecteuler.net/index.php?section=problems&id=93 とりあえず素直に全生成して、探索。 import Data.List import Data.Ratio perm [] = [[]] perm xs@(_:_) =concat[map (h:)$perm(delete h xs)|h<-xs] calc fs xs = concatMap (calc' fs) . perm …