A16 - 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

方針

ごく単純な動的計画法で対応できます.

解説1: 配列とfold

問題の通りに前から決めます. はじめは一部屋しか進めないためAから選ぶしかなく, あとは一部屋前から来るか二部屋前から来るかのどちらかです. 最短時間を取るにはminを取ります. 最終的には次のように計算できます.

1
2
3
4
5
  (Array.create N 0, [|1..(N-1)|])
  ||> Array.fold (fun Xa i ->
    if i=1 then Xa.[i] <- Aa.[i-1] else Xa.[i] <- min (Aa.[i-1]+Xa.[i-1]) (Ba.[i-2]+Xa.[i-2])
    Xa)
  |> Array.last

解説2: メモ化再帰

注意

メモ化再帰による動的計画法も有名です. 試したところ, F#のデータ型であるMapで実装したTLEしてしまいました. 一方.NETのSystem.Collections.Generic.Dictionaryでは問題なく通ります. ここでは後者の実装を紹介します.

テンプレート

まずメモ化再帰用の次の関数はテンプレートとして自作ライブラリに収録するとよいでしょう. 以下で説明する実装自体も完全にパターンです.

1
2
3
4
5
6
7
  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec j =
      match memo.TryGetValue j with
        | exist, value when exist -> value
        | _ -> let value = f frec j in memo.Add(j, value); value
    frec

この関数の中のDictionaryとして定めたmemoが値をためるメモです. この関数の中で再帰関数のfrecを定義します. TryGetValueで既にメモ化された値があるか確認します. 既にあればメモ化された値を返し, そうでなければ別途引数として与えた関数fで値を計算し, メモに積んで計算された値を返します. 最後に返すのもこの再帰関数です.

関数fの処理

F#入門記事で再帰はループで書け, 典型的な処理はmapやfoldで書けると説明しました. ここではfoldに食わせた関数をほぼそのままfとして採用すればよいです. 具体的には次のように書きます.

1
2
3
4
  let f frec j =
    if j<=0 then 0 elif j=1 then Aa.[j-1]
    else min (Aa.[j-1] + frec (j-1)) (Ba.[j-2] + frec (j-2))
  memorec f (N-1)

解説を読みやすくするためfの呼び出し部分まで書いておきました. 上記のテンプレートのmemorecにfを食わせ, 配列+foldでArray.lastとして得た「最後の項」を得るためにN-1を食わせています. 解説1の配列とfoldは添字が小さい方から順に計算した一方, メモ化再帰ではほしいN-1を食わせて添字が小さい方の降りる形になっています.

さてfを解説します. これはif j <= 0を追加した分が解説1のfと変わっているだけで, fold版と本質的には同じ関数です. foldでは添字が小さい方から計算していたためXa.[j-1], Xa.[j-2]などとした分が, メモから呼び出すために再帰関数の呼び出しに変わっています. ちなみにこのfrecはmemorecの内部で作っているfrecが入る部分です. 慣れないとこのfrecがどこから来るのかと混乱するかもしれません. 上記コードのように関数の名前や引数名をきちんと揃えておくと参照しやすいでしょう.

まとめ

コードの全体は次のように書けます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
let solve N (Aa:int[]) (Ba:int[]) =
  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec j =
      match memo.TryGetValue j with
        | exist, value when exist -> value
        | _ -> let value = f frec j in memo.Add(j, value); value
    frec
  let f frec j =
    if j<=0 then 0 elif j=1 then Aa.[j-1]
    else min (Aa.[j-1] + frec (j-1)) (Ba.[j-2] + frec (j-2))
  memorec f (N-1)

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