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_sum s n ls
|> 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_sum :: Int Int [Int] -> [[Int]]
comb_sum 0 0 _ = [[]]
comb_sum _ 0 _ = []
comb_sum s _ [] = []
comb_sum s n [e:rr]
| e > s
= comb_sum s n rr
= map ((:>) e) (comb_sum (s-e) (n-1) rr) ++ comb_sum s n rr
/*
//1. filterの部分をrest_of関数で置き換え
search [] = [[]]
search ls
= comb_sum s n ls
|> map (\f = let rr = rest_of f ls
in [[f:t] \\ t <- search rr])
|> foldr (++) []
rest_of _ [] = []
rest_of es=:[e:ee] ls=:[l:ll]
| l <= e = rest_of es ll
= rm ee ls
where
rm _ [] = []
rm [] ls = ls
rm es=:[e:ee] ls=:[l:ll]
| l < e = [l: rm es ll]
| e == l = rm es ll
= rm ee ls
//2. searchで直接グループわけの個数を計算
search [] = 1
search ls
= comb_sum s n ls
|> map (\f = let rr = rest_of f ls
in search rr)
|> sum
*/
lethevert
#5217()
[
Clean
]
Rating3/3=1.00
いくつか高速化を試して、一番効果の高かったcomb_sumでの置き換えだけを適用したもの。
n=5で、2分20秒
効果があまりなかったものは、コメントに記述してあります。
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_sum s n ls |> 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_sum :: Int Int [Int] -> [[Int]] comb_sum 0 0 _ = [[]] comb_sum _ 0 _ = [] comb_sum s _ [] = [] comb_sum s n [e:rr] | e > s = comb_sum s n rr = map ((:>) e) (comb_sum (s-e) (n-1) rr) ++ comb_sum s n rr /* //1. filterの部分をrest_of関数で置き換え search [] = [[]] search ls = comb_sum s n ls |> map (\f = let rr = rest_of f ls in [[f:t] \\ t <- search rr]) |> foldr (++) [] rest_of _ [] = [] rest_of es=:[e:ee] ls=:[l:ll] | l <= e = rest_of es ll = rm ee ls where rm _ [] = [] rm [] ls = ls rm es=:[e:ee] ls=:[l:ll] | l < e = [l: rm es ll] | e == l = rm es ll = rm ee ls //2. searchで直接グループわけの個数を計算 search [] = 1 search ls = comb_sum s n ls |> map (\f = let rr = rest_of f ls in search rr) |> sum */Rating3/3=1.00-0+
[ reply ]