069 C - Align

解説

はじめに

公式解説の他にもいくつか解答を見ていると, 偶奇で場合分けをしているコードもあれば, 一本で計算しきっているコードもありました. ただ私にはあまり直観的でなくすっと理解しにくかったため, ここではcojnaさんのコード例を参考にした実装を紹介します.

簡単な方針

大きな数値から小さな数値を引いた方がよいのは明らかです. ソートして大きい数のリストhsと小さい数のリストlsにわけ, 大きい数と小さい数を順に並べ続ければいいでしょう. 特に分けたリストを再帰的に先頭から取れば十分です.

問題は全要素数が奇数の場合の処理で, hsとlsから一つずつ取り続けて余った項をどこに置くかが問題です.

具体例で実装

入力例1で上の方針を追いかけます.

1
let N, Aa = 5, [|6L;8L;1L;2L;3L|]

まずは「ソートして大きい数のリストhsと小さい数のリストlsにわけ」の部分を実装します.

1
2
3
4
5
6
#r "nuget: FsUnit"
open FsUnit

let (xs,ys) = Aa |> Array.sort |> Array.toList |> List.splitAt (N/2)
xs |> should equal [1L; 2L]
ys |> should equal [3L; 6L; 8L]

大きい方は大きい順に取るためList.revで順序を反転します.

1
2
3
4
5
#r "nuget: FsUnit"
open FsUnit

let zs = ys |> List.rev
zs|> should equal [8L; 6L; 3L]

あとはxsとzsの先頭から再帰的に処理します. 再帰関数をfrecとして次のような呼び出しを前提にしましょう.

1
2
3
4
let (xs,ys) = Aa |> Array.sort |> Array.toList |> List.splitAt (N/2)
let (l,ls) = (List.head xs, List.tail xs)
let (h,hs) = ys |> List.rev |> fun zs -> (List.head zs, List.tail zs)
frec (h-l) l h (ls,hs)

はじめから初項を分離しなくてもいいとは思いますが, cojnaコードに合わせています. h-lの部分が結果を積むaccumlator変数です. hはhigh, lはlowで値の大小の分割を表しています. 最後の(ls,hs)はタプルにせず分けても構いません. 次の実装を前提にタプルにしています.

さて, 再帰関数の本体を考えましょう.

1
2
3
4
let rec frec acc low high = function
  | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h (ls,hs)
  | [],[h] -> acc + ???
  | _,_ -> acc

functionの部分は次の省略表記です.

1
2
3
4
5
let rec frec acc low high (xs,ys) =
  match (xs,ys) with
    | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h (ls,hs)
    | [],[h] -> acc + ???
    | _,_ -> acc

これは次のように書いても構いません.

1
2
3
4
5
let rec frec acc low high xs ys =
  match (xs,ys) with
    | (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h ls hs
    | [],[h] -> acc + ???
    | _,_ -> acc

以下前者のコードを前提に考えます. まずパターンマッチのmatchの第一行から考えましょう.

1
2
let rec frec acc low high xs ys =
  (l::ls),(h::hs) -> frec (acc + h-low + high-l) l h ls hs

まさにリストを先頭と残りに分割して処理しています. 再帰呼び出しのacc + h-low + high-lの項は, 一つ前の先頭の項に対して大きい数と小さい数の差を取るそのままの処理です. low, high, xs, ysの項も分割した項をそのまま積めば問題ありません.

残り二行を確認しましょう.

1
2
3
4
let rec frec acc low high xs ys =
  match (xs,ys) with
    | [],[h] -> acc + ???
    | _,_ -> acc

[],[h]は項数が奇数の場合の余りの処理で, 最後の_,_が項数が偶数の場合の処理です. 後者は積み切った値を素直に返せばよく何も考える必要はありません. したがってあとは一つ余った項の処理だけです.

結論から言えばmax (h-low) (high-h)です. はじめにsplitAt (N/2)でわけました. この分け方で最後の項がlsとhsのどちらに入るか変わります. どうしても揺れが起こるためmaxでその揺れを吸収しています.

入力例1と新たに作った以下のもう一つの入力例をもとに確認しましょう.

入力例1での最後の余りの処理は次のようになります.

1
2
3
4
5
6
7
8
9
xs -> [1L; 2L]
ys -> [8L; 6L; 3L]

low -> 2L
high -> 6L
h -> 3L

h-low -> 1L
high-h -> 3L

したがってこちらはhigh-hを取るべきです. 具体的に全体としてどのような並び方を選んだのかを考えるのも大事です. 実際には次のようになっています.

つまり初項を大きい方から取るか, 小さい方から取るかが最後の取り方で決まります.

さて, 新たな入力例はlet Aa = [|1L;4L;5L|]とします. この余りの処理は次のようになります.

1
2
3
4
5
6
7
8
9
Aa -> [|1L;4L;5L|]
xs -> [1L]
ys -> [5L;4L]

low -> 1L
high -> 5L
h -> 4L
h-low -> 3L
high-h -> 1L

入力例1と違ってh-lowを取るべきです. 具体的に全体としてどのような並び方を選んだかと言えば次の通りです.

もちろん他の可能性がないかも考えるべきではありますが, 前の項との差を取るアルゴリズムの組み方からしてありうるのはこの二通りしかありません. あとはこれを一般的にきちんと書き切れば適切なコードができます.