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 , set $ xs ++ repeat 9)
p206 :: Int -> Integer
p206 n = (10*).head.filter check.concatMap sqRange $ prefixs
where prefixs = sequence.replicate n $ [..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が速かった。