DouKaku? 4861 xsd: 出題者です。私の用意した方法も#...(魔方分割数)

Comment detail

出題者です。

私の用意した方法も#4835 minkeさんと同じ戦略で、ビットマスクを使うことを想定していました。
(ビットマスクを使っていない#4833 kozimaさんの方法が意外に速くて驚きました。)

それ以外は特に凝ったことはしていませんが、OCamlの再帰とmallocのコストが低いおかげで、2秒くらいで答えが出ました。

[xsd@celldev dk108]$ time ./dk108 5
3245664

real    0m2.056s
user    0m2.054s
sys     0m0.002s

let magic n =
    let m mask a = mask lor (1 lsl (a-1)) in
    let rec loop n r c mask acc =
        if c = 0 || r > (n*c-(n*(n-1)/2)) then acc else (
            if n = 1 then (
                if r <= c then (m mask r) :: acc else acc
            ) else (
                let x = r - c in
                let acc =
                    if x > 0 then
                        loop (n-1) x (min (c-1) x) (m mask c) acc
                    else
                        acc in
                loop n r (c-1) mask acc
            )
        ) in
    let rec filter mask acc = function
        | [] -> acc
        | hd :: tl -> filter mask (if (hd land mask) <> 0 then acc else hd :: acc) tl in

    let rec search n mask acc = function
        | []        -> acc
        | hd :: tl  ->
            if (mask land hd) <> 0 then
                let tl = if n > 1 then filter mask [] tl else tl in
                    search n mask acc tl
            else (
                if n = 1 then
                    acc + 1
                else (
                    let acc = search (n-1) (mask lor hd) acc tl in
                    search n mask acc tl
                )
            ) in
    search n 0 0 (loop n (n*(n*n+1)/2) (n*n) 0 [])

let _ = Printf.printf "%d\n" (magic (int_of_string Sys.argv.(1)))

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq