競技プログラミングのためのF#入門
GitHub上の対応ディレクトリ 公式ページ 要点: アルゴリズム 入出力
| 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
を取ります. 最終的には次のように計算できます.
| (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
では問題なく通ります. ここでは後者の実装を紹介します.
テンプレート
まずメモ化再帰用の次の関数はテンプレートとして自作ライブラリに収録するとよいでしょう. 以下で説明する実装自体も完全にパターンです.
| 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
として採用すればよいです. 具体的には次のように書きます.
| 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
|
Previous: A15 - Compression Next: A17 - Dungeon 2 back to top