ABC108-D:Robot Arms

問題

https://beta.atcoder.jp/contests/abc111/tasks/arc103_b

制約

  • 1 \le N \le 1000
  •  |X_i|,\ |Y_i| \le 10^9

考え方

必要条件を考える

まず、構成するための必要条件を考える。m つの腕を定めたときに n つの点が同時に到達できないといけない。これはそれぞれの点の距離 x_i + y_i についてその偶奇が一致していないといけない。偶奇が一致していれば、十分な数の距離 1 の腕を使えば構成できることはわかる。

構成方法を考える

原点から (x_i,\ y_i) に到達するように d_i を定めないといけない。使える腕の数が 1 \le m \le 40 と小さいので工夫して構成する必要がある。

「任意の数を作る」ときに 2 冪で構成することはよく知られている。1,2,4,\cdots,2^{30} の腕を使って x_i を作ることができる。

さて、難しいのは x_i, y_i を同時に到達するようにモードを定めることである。これは実は座標を 45 度変換することで解決できる。

  • u = x + y
  • y = x - y

f:id:d_tutuz:20181209220107p:plain

として u-v 座標で考えることとすると、モードによる操作は以下のように変換されることがわかる。

x y u v
L - 0 \to - -
R + 0 \to + +
U 0 + \to + -
D 0 - \to - +

変換された後の操作は、ある操作で uv のそれぞれについて同時に座標を加減することができる。そうすると後は、2 冪で構成された腕の長さの長い腕( d=2^{30} )から貪欲に当てはまるモードを設定すれば良い。なお (x_i, y_i) から原点への移動方法を考えるがモードの設定は移動の方向と逆向きのモードを設定する。

1,2,4,\cdots,2^{30} の腕を用いる場合は任意の奇数のみを構成できるが、偶数の場合は長さ 1 の腕を加えれば良い。

Submission #3766414 - AtCoder Beginner Contest 111

どこに着目して考察するべきだったか

任意の数を効率よく構成する方法は 2 冪で考えることである。加えて、xy 座標上の 2 変数に対して同時に操作したい場合は、座標変換して uv 座標上で考えるとうまくいくかもしれない。

何がバグっていたか

得た知見

  • 2 冪で構成
  • 座標変換(45度回転)

類題