A17 - Dungeon 2

入出力

1
2
3
4
let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

方針

これもA16と同じ動的計画法を少し修正すれば対応できます. 経路を積む処理を明確にするため配列の初期化法が少し変えました.

解説1: 配列とfold

単純に時間の計算に加えて経路の情報を積むだけです. コードを読みやすくするために変数を用意しただけで, 本質的にはA16と変わりません.

具体的にはリターンする配列の各要素をタプルにして, fstは経路のリスト, sndは時間にしているだけです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
let solve N (Aa:int[]) (Ba:int[]) =
  Array.create N ([],0)
  |> fun Xa ->
    Xa.[0] <- ([1],0)
    Xa.[1] <- ([2;1],Aa.[0])
    Xa
  |> Array.fold (fun Xa i ->
    let (xs,x) = Xa.[i-1]
    let (ys,y) = Xa.[i-2]
    let (a,b) = (Aa.[i-1],Ba.[i-2])
    Xa.[i] <- if y+b<x+a then ((i+1)::ys, y+b) else ((i+1)::xs, x+a)
    Xa) [|2..N-1|]
  |> (Array.last >> fst >> List.rev)
  |> fun Xs -> sprintf "%d\n%s" (Xs.Length) (Xs |> List.map string |> String.concat " ")

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

解説2: メモ化再帰

これも関数の返り値が変わるだけです. このくらい簡単な内容ならどちらも完全に定型処理にはめるだけです. 読み書きしやすい方で対処してください.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let solve N (Aa:int[]) (Ba:int[]) =
  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec k =
      match memo.TryGetValue(k) with
        | true, v -> v
        | _ -> let v = f frec k in memo.Add(k,v); v
    frec
  let f frec k =
    if k=0 then ([1],0)
    elif k=1 then ([2;1],Aa.[0])
    else
      let (xs,x) = frec (k-1)
      let (ys,y) = frec (k-2)
      let (a,b) = (Aa.[k-1],Ba.[k-2])
      if y+b<x+a then ((k+1)::ys, y+b) else ((k+1)::xs, x+a)
  memorec f (N-1) |> (fst >> List.rev)
  |> fun Xs -> sprintf "%d\n%s" (Xs.Length) (Xs |> List.map string |> String.concat " ")

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine