236 Luxury Hampers

Problem 236 – Project Euler

とりあえず，問題文が長いし，すこし複雑．

それを除いても，この問題は難しいと思われる．

たぶん，重要なのは，この問題がどの種類の問題か判別すること（整数論とか，探索とか）だと思う．

とりあえず，探索問題と捉えた．そこで，考えるのは，全探索は無理なので，どう枝刈りして，探索をサボるか．

鍵となるのは，個々の spoilage rates はBのほうが悪いけど， 全体の spoilage rates はAのほうが悪いという点，だと思った．

で，計算していたら，ちょっと違ったかたちだが，良い必要条件が得られたので，それを利用．

三つの品物をまとめて考えることができるので，探索範囲がせまくなった(これが重要）． 

import Data.List (sort)
import Data.Ratio ((%), numerator, denominator)
reducedForm :: Rational -> (Integer, Integer)
reducedForm r = (numerator r, denominator r)
a, b :: [Integer]
a = [5248, 1312, 2624, 5760, 3936, sum $ take 5 a]
b = [640, 1888, 3776, 3776, 5664, sum $ take 5 b]
k :: [Rational]
k = zipWith (%) a b
x3s :: Rational -> [Integer]
x3s m = [ l * d | l <- [1..min ( a!!3 `div` d) ( b!!3 `div` n)] ]
where (n, d) = reducedForm $ m / k!!3
sum03 :: (Integral a, Integral a1) => Rational -> a -> a1 -> Rational
sum03 m x0 x3 = fromIntegral x0 * (1 - k!!5 / k!! * m ^ 2) + fromIntegral x3 * (1 - k!!5 / k!!3 * m ^ 2)
check124 :: (Integral a1, Integral a) => Rational -> a -> a1 -> Bool
check124 m x0 x3 = r ==  && mod x d ==  && 3 <= div x d && div x d <= upp
where [(n, d), (f, g), (u, v)] = map reducedForm $ [m / k!!1, sum03 m x0 x3, k!!5 / k!!1 * m ^ 2 - 1]
(x, r) = divMod (f * v) (g * u)
upp    = sum $ zipWith min [a!!1 `div` d, a!!2 `div` d, a!!4 `div` d]
[b!!1 `div` n, b!!2 `div` n, b!!4 `div` n]
p236 :: [(Rational, Integer)]
p236 = [(m, x0) | x0 <- [1..a!!] , y0 <- [1..b!!], let m = k!! * (y0 % x0), m > 1, isSpecial m x0]
where isSpecial m x0 = or [check124 m x0 x3 | x3 <- x3s m]
main :: IO ()
main = print.fst.last.sort $ p236

解を全列挙しているし，おなじ m を何度も求めているので，効率が良くないし，

アルゴリズムもそんなにスマートではない気がする．

しかし，デスクトップPCで実行したら，5秒以下だったので良しとする．