DouKaku? 4492 shiro: ナイーブに、分割してから長さでソート。時...(自然数の分割（別表現）)

Comment detail

ナイーブに、分割してから長さでソート。時間とファイルサイズはこんな感じ (on Pen4 2GHz, Linux, GHC6.6.1, compiled)。なお50の場合の解の総数は204226個でした。合ってる?

[shiro@scherzo ~]$ time ./Main > /dev/null

real 0m17.715s
user 0m16.241s
sys 0m0.489s
[shiro@scherzo ~]$ time ./Main > x

real 0m20.210s
user 0m17.327s
sys 0m1.230s
[shiro@scherzo ~]$ ls -l x
-rw-rw-r-- 1 shiro shiro 33643344 Nov 29 16:43 x

module Main where
import Data.List
import qualified System.IO.UTF8 as U

partitionNum n = sortBy cmp $ pttn n n
  where cmp a b | length a < length b  = LT
                | length a == length b = EQ
                | otherwise            = GT
        pttn 0 _ = [[]]
        pttn n k = [(n-x):xs | x <- [max (n-k) 0..n-1], xs <- pttn x (n-x)]

main = U.putStr $ unlines $ foldr chunk [] $ partitionNum 50
  where chunk ns r = map (\n -> replicate n '□') ns ++ [""] ++ r

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq