結果

問題 No.44 DPなすごろく
ユーザー esehara
提出日時 2021-06-10 12:54:57
言語 OCaml
(5.2.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 990 bytes
コンパイル時間 1,237 ms
コンパイル使用メモリ 20,904 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 20:31:49
合計ジャッジ時間 2,085 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

module Closure: sig
  val memo_with : ('a -> 'b) -> 'a -> 'b
  val memo_rec: (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
  val memo_rec_with: ('a -> ('b -> 'c) -> 'b -> 'c) -> 'a -> 'b -> 'c
end = struct
  let memo_rec f =
    let h = Hashtbl.create 10000 in
    let rec g x =
      let try_find = Hashtbl.find_opt h x in
      match try_find with
      | Some (x) -> x
      | None ->
        let y = f g x in
        Hashtbl.add h x y ;
        y
    in
    g;;
  let memo_with f arr = f arr;;
(*

Usage:

let rec sushi_as_fib sushi_array self x =
if x < 1 then 0
else max ((self (x - 2)) + sushi_array.(x - 1)) (self (x - 1));;

=> (array -> self -> 'a) = f: 'a -> 'b

let sushi = Closure.memo_rec_with sushi_as_fib sarray;;
*)
  let memo_rec_with f farr = memo_rec (memo_with f farr);;
end

let rec dice_as_fib self x =
  if x < 2 then 1 else (self (x - 1)) + self (x - 2);;

let sugoroku = Closure.memo_rec dice_as_fib;;

let () =
  read_int () |> sugoroku |> print_int;
  print_newline ();;
0