結果

問題 No.437 cwwゲーム
ユーザー ichibanshibori
提出日時 2016-10-31 16:43:13
言語 OCaml
(5.2.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,023 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 17,792 KB
最終ジャッジ日時 2024-11-14 19:53:35
合計ジャッジ時間 585 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
File "Main.ml", line 7, characters 17-28:
7 |     try Some (f (Stream.next stream))
                     ^^^^^^^^^^^
Error: Unbound module Stream

ソースコード

diff # 

let int_array_of_string str =
  Array.init (String.length str)
             (fun idx -> int_of_char str.[idx] - int_of_char '0')

let stream_map f stream =
  let rec next _ =
    try Some (f (Stream.next stream))
    with Stream.Failure -> None
  in
  Stream.from next

let stream_filter p stream =
  let rec next i =
    try
      let value = Stream.next stream in
      if p value then Some value else next i
    with Stream.Failure -> None
  in
  Stream.from next

let combinations arr n =
  let comb_arr = Array.init n (fun i -> i)
  and larr = Array.length arr
  and n_1 = n - 1
  in
  let rec count_up idx =
    if comb_arr.(idx) < larr - n + idx then (
      comb_arr.(idx) <- comb_arr.(idx) + 1;
      true)
    else if idx = 0 then false
    else (
      comb_arr.(idx) <- -1;
      count_up (idx - 1))
  in
  let rec reinit_comb idx =
    if idx < n then (
      if comb_arr.(idx) = -1 then (
        comb_arr.(idx) <- comb_arr.(idx - 1) + 1);
      reinit_comb (idx + 1))
  in
  let get_comb_array () =
    Array.map (fun i -> arr.(i)) comb_arr
  in
  let is_first = ref true in
  Stream.from (fun _ ->
    if !is_first then (
      is_first := false;
      Some (get_comb_array ()))
    else (
      if count_up n_1 then (
        reinit_comb 1;
        Some (get_comb_array ()))
      else None))

let stream_max_by f st =
  let max_val = ref 0 in
  Stream.iter
    (fun v -> let iv = f v in
              if iv > !max_val then max_val := iv)
    st;
  !max_val

let array_filter f arr =
  let larr = Array.length arr in
  if larr <= 0 then [||]
  else
    let buf = Array.make larr arr.(0)
    and len = ref 0 in
    Array.iter (fun v -> if f v then (
                           buf.(!len) <- v;
                           len := !len + 1))
               arr;
    Array.init !len (fun i -> buf.(i))



let solve narr =
  let rec solve' cur_score rest_arr =
    let larr = Array.length rest_arr
    and rest_arr2 = Array.mapi (fun l v -> (l, v)) rest_arr
    in
    let conv_arr iarr =
      let i, j, k = iarr.(0), iarr.(1), iarr.(2) in
      let c, w1, w2 = rest_arr.(i), rest_arr.(j), rest_arr.(k) in
      ((i, j, k), (c, w1, w2))
    in
    let conv_cww ((i, j, k), (c, w1, w2)) =
      let cww = c * 100 + w1 * 10 + w2
      and next_rest_arr =
        array_filter (fun (l, _) -> l <> i && l <> j && l <> k) rest_arr2 |>
        Array.map (fun (_, v) -> v)
      in
      (cur_score + cww, next_rest_arr)
    in
    if larr < 3 then cur_score
    else
      let iarr = Array.init larr (fun i -> i) in
      let st = combinations iarr 3 |>
               stream_map conv_arr |>
               stream_filter
                 (fun (_, (c, w1, w2)) -> c <> 0 && c <> w1 && w1 = w2)
      in
      match Stream.peek st with
      | None -> cur_score
      | _ ->
        stream_map conv_cww st |>
        stream_max_by (fun (score, next_rest_arr) -> solve' score next_rest_arr)
  in
  solve' 0 narr

let () =
  let narr = read_line () |> int_array_of_string in
  solve narr |> string_of_int |> print_endline
0