module Main
import Bool, Int, List, Array, ValueCast, StringCast, System, Misc
Start = length $ divide n s ls
where
n = toInt getCommandLine.[1]
ls = [1..n*n]
s = sum ls / n
divide n s ls = search ls
where
search [] = [[]]
search ls
= comb n ls
|> filter (\f = sum f == s)
|> map (\f = let
(f0,fr) = (head f, tail f)
rr = filter (\e = not (e <= f0 || fr contains e)) ls
in [[f:t] \\ t <- search rr])
|> foldr (++) []
comb :: Int [a] -> [[a]]
comb 0 _ = [[]]
comb _ [] = []
comb n [e:rr]
= map ((:>) e) (comb (n-1) rr)
++ comb n rr
lethevert
#5216()
[
Clean
]
Rating0/0=0.00
とりあえずナイーブに実装。
n=4の場合、0.04秒ですが、n=5の場合、5分経っても終わらないです。
see: AltEnvライブラリを使っています
module Main import Bool, Int, List, Array, ValueCast, StringCast, System, Misc Start = length $ divide n s ls where n = toInt getCommandLine.[1] ls = [1..n*n] s = sum ls / n divide n s ls = search ls where search [] = [[]] search ls = comb n ls |> filter (\f = sum f == s) |> map (\f = let (f0,fr) = (head f, tail f) rr = filter (\e = not (e <= f0 || fr contains e)) ls in [[f:t] \\ t <- search rr]) |> foldr (++) [] comb :: Int [a] -> [[a]] comb 0 _ = [[]] comb _ [] = [] comb n [e:rr] = map ((:>) e) (comb (n-1) rr) ++ comb n rrRating0/0=0.00-0+
[ reply ]