073 C - Strange Bank

解答1: 公式解説, シンプルなループ処理

公式解説の処理をF#で単純に書き直すならこのコードのようになるでしょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
open System
let n : int = int(Console.ReadLine())
let mutable res = n
let mutable i = 0
while i <= n do
    let mutable cc = 0
    let mutable t = i
    while t > 0 do
        cc <- cc + t % 6
        t <- t / 6
    t <- n - i
    while t > 0 do
        cc <- cc + t % 9
        t <- t / 9
    if res > cc then
        res <- cc
    i <- i + 1
printfn "%d" res

最初のwhile i <=n doはforで簡単に書き換えられるとして, 可変変数を不変変数に置き換えつつ, 内部のwhile t > 0 doをどう関数型らしく書き換えるかがまず問題です. F#解説に書いたように再帰で書き換えます.

tは各whileの直前で設定し直していて最終的にccを返せばよいため, tは単純に関数の入力パラメータにすればよいでしょう. 6で割るwhileループを表す再帰関数は次のように書けます.

1
let rec frec cc t = if t>0 then frec (cc+t%6) (t/6) else cc

正の数を正の数で割り続けたあまりは0になるため, then節が短くなるように条件式を書き換えています. 9で割り続ける処理はmod kのkが変わるだけで同じ処理です. それもまとめた再帰関数は次のように書けます.

1
let rec frec k cc t = if t>0 then frec k (cc+t%k) (t/k) else cc

次にメインのwhile i<=n doを考えます. これは最終的に積んだ値resを返すループだからfoldを使えばよいでしょう. 結論としては次のように書けます.

1
2
3
4
5
6
let solve N =
  let rec frec k cc t = if t>0 then frec k (cc+t%k) (t/k) else cc
  (N,[|0..N|]) ||> Array.fold (fun res i ->
    let cc6 = frec 6 0 i
    let cc9 = frec 9 cc6 (N-i)
    if res <= cc9 then res else cc9)

最後のif式ではelseをつけ忘れないようにしましょう. もちろんつけないと型エラーで動きません.

最後に, そもそも意味がわからずはまり倒したため, let cc6 = frec 6 0 i; let cc9 = frec 9 cc6 (N-i)で何をしているかを説明する自分用のメモ. まず次のように書き換えて考えるといいでしょう.

1
2
    let cc6 = frec 6 0 i
    let cc9 = frec 9 0 (N-i)

こうすると次のように意味がはっきりします.

あとは全探索の部分です. ある数iを6のベキで処理し切ったら残りのN-iは9のベキで処理するしかありません. これを全探索で全てのiに対して確認しています.

解説2: ユーザ解説, メモ化再帰

ユーザ解説はDPで解いています. 私の前にF#でDPで解いている人がいます. 実行時間も短いためこれも考えてみましょう. 上記コードはちょっと長いため単純化したコードを紹介します. 2022-12時点で全てではないものの, Educational DP Contest / DP まとめコンテストにF#で取り組んだ結果があるため, こちらも参考にしてください. (2022-12時点では特にHaskell・OCamlコードを焼き直しただけで, 私は自力でDPを解く力量がありません.)

まずF#版のarray6とarray9にあたる配列生成を考えます. もちろんいくつか書き方はあり, 比較的簡潔なのは次のコードでしょうか.

1
2
3
  let rec p k x acc = if x>N then (acc-1) else p k (k*x) (acc+1)
  let array6 = [|0..(p 6 1 0)|] |> Array.map (pown 6)
  let array9 = [|0..(p 9 1 0)|] |> Array.map (pown 9)

再帰関数のpはベキを何回まで取ればいいか計算する関数です.

次は本丸のメモ化再帰です. 定型的な書き方があるため, コピペで使えるようにReference.fsxにメモしています.

まずはコードを示してそれにコメントしましょう.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
  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 count frec n =
    if n=0 then 0
    else
      let c1 = n - (array6 |> Array.findBack (fun x -> x<=n))
      let c2 = n - (array9 |> Array.findBack (fun x -> x<=n))
      1 + min (frec c1) (frec c2)
  (memorec count) N

メモ化の部分がlet memorec fです. let memo = System.Collections.Generic.Dictionary<_,_>()はF#のMapではなく.NETの辞書を読んでいます. memo.Addで破壊的に書き換わってくれた方が便利だからです. let rec frec jはメモがあればその値を返し, ない場合は値を詰めて返します.

処理の本体がcountです. 第一引数のfrecはmemorec中でfrecとして呼び出す関数で, 対応を明確にするために名前を揃えています.

まずc1から考えましょう. 6のベキで大きい方から削るため, (array6 |> Array.findBack (fun x -> x<=n))で削れる中で最大の数を取ります. c1は削って残った数で, frec c1でメモ化再帰または動的計画法でc1に辿り着くまでの最小操作回数が取れます. 実際にcount関数のelse節でprintfn "%A" (c1,c2,frec c1, frec c2)で出力して確認してみてください.

同じ計算を9に対しても適用して, 小さい方を取れば最小回数が得られます. 最後に1を足すのはmin (frec c1) (frec c2)は最終ステップ一手前の値だからです.

あとはcountにmemorecでガワをかぶせて計算すれば求める結果が得られます. メモ化のための辞書memoをクロージャーmemorecで隠蔽している分コードが読みにくいかもしれません. オリジナルは最終的に呼び出す関数が素直な再帰になっているため, こちらの方がわかりやすいかもしれません.