085 C - Pyramid

解説

公式解説通りに素直に実装します.

入出力

1
2
3
let N = stdin.ReadLine() |> int
let Aa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1],x.[2])
solve Aa |> stdout.WriteLine

補助関数

l1距離を測る関数l1を定義します.

1
  let l1 (x1,y1) (x2,y2) = abs(x1-x2) + abs(y1-y2)

はじめ l1 x1 y1 x2 y2で定義したものの, 間違って右辺の出てくる順番でl1 x1 x2 y1 y2と書いてバグったため, (私にとって)間違えにくいタプルで書き直しました.

参照点の選出

Array.findで探せます.

1
  let (x0,y0,h0) = Aa |> Array.find (fun (_,_,h) -> h<>0)

F#のnot equalはa <> bです. ちなみにHaskellではa /= bです.

問題の条件によって必ず条件をみたす点が存在するためArray.tryFindなどを使う必要はありません.

全探索

まず中心のデータを一気に生成します.

1
2
  [| for x in 0..100 do for y in 0..100 do x,y |]
  |> Array.map (fun (x,y) -> x, y, h0 + l1 (x,y) (x0,y0))

あとは再びArray.findで条件をみたす要素を探します. これも必ず, それも一意的に存在するとわかっているためArray.tryFindなどで保険をかける必要はありません.

全ての入力が条件をみたすか確認する必要があるため, Array.findの中でAaに対するチェックのループが走ります.

1
2
3
4
  [| for x in 0..100 do for y in 0..100 do x,y |]
  |> Array.map (fun (x,y) -> x, y, h0 + l1 (x,y) (x0,y0))
  |> Array.find (fun (x,y,h) ->
    Aa |> Array.forall (fun (xi,yi,hi) -> hi = max 0 (h - l1 (x,y) (xi,yi))))

最後に返り値の数値のタプルからsprintfで文字列を生成しましょう.

1
2
3
4
5
6
7
8
let solve Aa =
  let l1 (x1,y1) (x2,y2) = abs(x1-x2) + abs(y1-y2)
  let (x0,y0,h0) = Aa |> Array.find (fun (_,_,h) -> h<>0)
  [| for x in 0..100 do for y in 0..100 do x,y |]
  |> Array.map (fun (x,y) -> x, y, h0 + l1 (x,y) (x0,y0))
  |> Array.find (fun (x,y,h) ->
    Aa |> Array.forall (fun (xi,yi,hi) -> hi = max 0 (h - l1 (x,y) (xi,yi))))
  |> fun (x,y,h) -> sprintf "%d %d %d" x y h