掴み所がわからなかったけど理解すると面白そうな問題。

問題

$i=1,...,N$ について $(X_i, Y_i)$ が与えられる。

$d_j (j=0,...,M)$ をある値で固定したとき、すべての $i$ について $(X_i, Y_i) = \sum_{j=0}^m d_jf(a_j)$ が成り立つような $a_j=\{0,1,2,3\}$ の選び方は存在するか。ここで $f(0)=(1,0), f(1)=(-1,0), f(2)=(0,1), f(3)=(0,-1)$ とする。

解法

座標変換->二進展開->貪欲法という流れで解いていく。

座標変換

マンハッタン距離の問題は、45°回すテクがあるらしい。
ここでは $U=X+Y,V=X-Y$ とすれば、 $f(0)=(1,1), f(1)=(-1,-1), f(2)=(1,-1), f(3)=(-1,1)$ となる。
これでうれしいのは、 $g(0)=-1, g(1)=1$ としたときに] $X_i=\sum d_j g(a_j)$ と $Y_i=\sum d_j g(b_j)$ のようにXとYを独立に考えられるようになったこと。
座標変換前はdjをXかYを足すか引くかという操作だったのが、Uには足すか引くか、Vには足すか引くかというように別々に考えてよくなったというのがわかる。