マンハッタン距離

Manhattan Center (manhattan-center) | CSA

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。 これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする) P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。 x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のとき</x[k+1]とする)>…

Moving the Kings | HourRank 27

キングが中心にいる場合、キングから周囲のマスまでの移動は 22222 21112 21012 21112 22222 のようになっている。距離1のマスは45度回転すると のようになる。 すべて整数で表すために√2を掛けると 座標は(2, 0), (1, 1), (0, 2), (-1, 1), (-2, 0), (-1, -…