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秒以下だったので良しとする.