結果

問題 No.44 DPなすごろく
ユーザー eseharaesehara
提出日時 2021-06-10 12:54:57
言語 OCaml
(5.1.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 990 bytes
コンパイル時間 1,926 ms
コンパイル使用メモリ 20,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-07 06:11:14
合計ジャッジ時間 2,688 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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