Google Code Jam Japan 2011 予選問題B

coffee.fs

type Coffee = {c:int64; t:int64; s:int64}

let sub {c=c;t=t;s=s} c' = {c=c-c';t=t;s=s}

let take s (xs:Coffee list) d c =
  let rec take (xs:Coffee list) (ys:Coffee list) c s =
    match ys with
    | []      -> (s, List.rev xs)
    | y'::ys' -> if y'.t<d then
                   take (y'::xs) ys' c s
                 elif y'.c < c then
                   take ((sub y' y'.c)::xs) ys' (c-y'.c) (s+y'.c*y'.s)
                 else
                   (s+c*y'.s, List.rev xs @ (sub y' c)::ys')
  take [] xs c s

let spans (cs:Coffee list) =
  let ts = List.map (fun c -> c.t) cs
  let ts' =
    0L::ts
    |> List.sortWith (fun x y -> compare y x)
    |> Seq.distinct
  Seq.zip ts' (Seq.skip 1 ts') |> Seq.map (fun (t,t') -> (t,t-t'))

let solve (cs:Coffee list) =
  let ts = spans cs
  let cs' = List.sortWith (fun c1 c2 -> compare c2.s c1.s) cs
  Seq.fold (fun (s,xs) (d,c) -> take s xs d c) (0L,cs') ts
  |> fst

let nk (s:string) =
  let nk = stdin.ReadLine().Split([|' '|])
  (int nk.[0], int64 nk.[1])

let cts (s:string) =
  let a = s.Split([|' '|])
  {c=int64 a.[0]; t=int64 a.[1]; s=int64 a.[2]}

let t = int (stdin.ReadLine())
for i in 1..t do
  let (n,k) = nk (stdin.ReadLine())
  let cs =
    seq { for i in 1..n -> cts (stdin.ReadLine()) } |> Seq.toList
  printfn "Case #%d: %d" i (solve cs)