AtCoder ARC #103 : D - Robot Arms - kmjp's blog

途中離脱のためDEFはまともに考えられず。 https://beta.atcoder.jp/contests/arc103/tasks/arc103_b 問題 ２次元座標において、N個の座標が与えられる。 ここで、M個の腕をそれをつなぐ(M-1)個の関節からなるアームを持つロボットを考える。 このアームは原点にいるロボットから生えており、間接毎に次の腕の向きを上下左右にできるものとする。 アームの先端がN個の座標すべてに到達できるようなアームの腕の長さを答えよ。 解法 まず前提として腕の向きをどうしても先端の座標のパリティは変わらないので、N個の座標のパリティが一致することは先に確認しておこう。 以下パリティが奇数の場合を考える。偶数の場合最後にの長さ1の腕を追加すればよい。 腕の長さを1,2,4,8,...とする。 実は2^0～2^kの腕があると、原点からマンハッタン距離が2^(k+1)

[tinsep19]

“実は2^0～2^kの腕があると、原点からマンハッタン距離が2^(k+1)-1以下のパリティが奇数の点はすべて到達できる。”