Problem 103

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` 2]
    where f ys n = (sum.take (n+1)) ys > (sum.take n.reverse) ys

subsetSumNeq xs = all (f xs) [1..length xs `div` 2]
    where f ys n = all (null.tail).group.sort.map sum. comb ys $ n

specialSum xs = monotone xs &&  subsetSumNeq xs

main = print.minimumBy(comparing sum)$[x|x<-comb [20..50] 7,specialSum x]

comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)

ま、遅いけど。いいんじゃん。よく分からない問題だし。

Problem 99

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 = maximumBy (comparing $ foldl1 logPow)$xs
          print.findIndex (==ans) $ []:xs
    where g x = "["++ x ++"]"

Problem 100

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

import Data.List
naive m = [(n,d)|d<-[1..m],n<-[div d 2..d],2*n*(n-1)==d*(d-1)]
next (x,y) = (3*x+4*y,2*x+3*y)
toDisc (x,y) = ((y+1)`div`2,(x+1)`div`2)
p100 = map toDisc.iterate next $ (1,1)
main = print.find ((>10^12).snd)$p100

Problem 101

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

gen = foldr f 1 .replicate 10
    where f x y = 1 - x*y
diff xs = zipWith (-) (tail xs) $ xs
bOP g n = sum.map last.take n.iterate diff.take n.map g $ [1..]
main = print.sum.map (bOP gen)$[1..10]

Problem 102

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) xs || all (<0) xs
toTuples = unfoldr t
    where t [] = Nothing
          t (x:y:zs) = Just ((x,y),zs)
main = do f <-readFile $ "triangles.txt"
          print.length.filter (containO.triangle).lines$f
    where triangle x = toTuples.read$"["++ x ++ "]" ::[(Int,Int)]