071 C - Linear Approximation

解説

公式解説通り入力Aaをシフトした配列をBaとします. 解説の便宜のためBaをソートした配列をCaとしましょう.

公式解説通りに実装すれば問題ありません. 他の人のコードを見ていると中央値の扱いにぶれがあるようです. 単にBa.[N/2]だけとしているコードもあれば, 偶奇でわけたコードもあります.

ちなみに私はさらに違う処理にしました. 選ぶべきbが整数でなければならないため, Nが奇数のときはCa.[N/2], Nが偶数のときはCa.[N/2]とCa.{N/2-1}を中央値の候補としています. もちろんNが偶数のときは二つの値を計算して小さい方を取ります.

どう書くとすっきりするかは人によるものの, 私は中央値の候補を配列にして処理しました. 具体的には次のように中央値の候補を作っています.

1
2
  let Ba = Aa |> Array.mapi (fun i a -> a - (int64 (i+1)))
  let Ma = Ba |> Array.sort |> fun Ba -> if N%2=1 then [|Ba.[N/2]|] else [|Ba.[N/2-1];Ba.[N/2]|]

最終的な悲しさの最小値は中央値の配列Maから次のように計算しています.

1
  Ma |> Array.map (fun b -> Ba |> Array.sumBy (fun x -> abs(x-b))) |> Array.min

よほど複雑な処理をかませる場合は適切な対処が必要ですが, Array.map f |> Array.sumはArray.sumByで書くとすっきりします.

私がはまり倒したため念のため書いておきます. 次のように書くとMaの値を取ってしまい正しい悲しさの最小値が得られません.

1
  Ma |> Array.minBy (fun b -> Ba |> Array.sumBy (fun x -> abs(x-b)))

おまけ

次の二つのコードの結果が面白いです.

1
2
3
4
let n = int (stdin.ReadLine())
let a = stdin.ReadLine().Split() |> Array.mapi (fun i x -> int64 x - int64 i - 1L) |> Array.sort
let b = if n % 2 = 0 then (a.[n / 2] + a.[n / 2 - 1]) / 2L else a.[n / 2]
printfn "%d" (Array.sumBy (fun x -> abs (x - b)) a)

1
2
3
4
let n = int (stdin.ReadLine())
let a = stdin.ReadLine().Split() |> Array.mapi (fun i x -> int64 x - int64 i + 1L) |> Array.sort
let b = if n % 2 = 0 then (a.[n / 2] + a.[n / 2 - 1]) / 2L else a.[n / 2]
printfn "%d" (Array.fold (fun (l : int64) k -> l + abs (k - b)) 0L a)

違うのは最後の和を取る部分でsumByなのかfoldかです. 実行時間は変わらないものの消費メモリが一割違います. 少なくともMono 4.0でメモリ効率を考えるならfoldの方がよいようです.

そしてさらに私の提出コードも見てみましょう.

1
2
3
4
5
6
7
8
let solve N Aa =
  let Ca = Aa |> Array.mapi (fun i a -> a - (int64 (i+1)))
  let Ba = Ca |> Array.sort |> fun Ba -> if N%2=1 then [|Ba.[N/2]|] else [|Ba.[N/2-1];Ba.[N/2]|]
  Ba |> Array.map (fun b -> Ca |> Array.sumBy (fun x -> abs(x-b))) |> Array.min

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

偶数項のとき和を二回取っているため明らかにこちらの方が遅いはずですが, Mono 4.0よりも高速です. Mono 4.0のリリースが2015年, .NET core 3.1.201のリリースが2021年で後者の方が新しいため, 処理系の高速化のおかげでしょう.