Problem 206

Project Euler Haskell

206 Concealed Square
Problem 206 - Project Euler
全探索しては身も蓋もないので、すこし工夫しましょう。という問題なんでしょうか？
はじめの分からない数字を一つ定めると、先頭3桁の数字が決まる。
つまり、探索範囲が減ってそう。この観察と、
\sqrt{l+d}-\sqrt{l}=\frac{d}{\sqrt{l+d}+\sqrt{l}}\leq\frac{d}{2\sqrt{l}}
から、分からないはじめのn個の数字を固定したときの計算量は、非常に大雑把に見積って、
\frac{1}{2}10^{8-n}+10^{n}
ぐらい。ということは、多分3個か4個、固定してやるのが一番よい？

tie :: [a] -> [a] -> [a]
tie [] _ = []
tie _ [] = []
tie (x:xs) (y:ys) = x:y:tie xs ys

set :: [Int] -> Integer
set = foldl1 (\a b -> a*10+b).map toInteger.init.tie ([1..9])

pick :: [a] -> [a]
pick = map head.takeWhile (not.null).iterate (drop 2)

range :: [Int] -> (Integer, Integer)
range xs = (set $ xs ++ repeat 0, set $ xs ++ repeat 9)

p206 :: Int -> Integer
p206 n = (10*).head.filter check.concatMap sqRange $ prefixs
    where prefixs = sequence.replicate n $ [0..9]
          check = ("123456789" ==).pick.show.(^2)
          sqRange xs = let (l,u) = range xs
                       in [floor.sqrt' $ l .. ceiling.sqrt' $ u]
          sqrt' = sqrt.fromIntegral

main :: IO ()
main = print.p206 $ 3

3が速かった。