Problem 236

Project Euler Haskell

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!!0 * 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 == 0 && mod x d == 0 && 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!!0] , y0 <- [1..b!!0], let m = k!!0 * (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秒以下だったので良しとする．