ARC103 D. Robot Arms

問題

m本の腕とm+1個の関節からなるロボットアームを考える。
腕iの長さはd_i。
関節iは腕iと腕i+1をつないでおり、関節1は原点に置かれ、各関節の角度は上下左右方向に指定できる。

いま、N個の平面上の整数点が与えられる。
すべての整数点にぴったり関節m+1を合わせられるようなロボットアームを返せ。
また、各整数点について、実際にその点に合わせられるような関節の指定値を出力せよ。
できない場合は-1を出力せよ。

制約

• 入力はすべて整数
• 1 <= N <= 1000
• -10^9 <= X_i, Y_i <= 10^9
• 1 <= m <= 40
• 1 <= d_i <= 10^12, d_iは整数

解法

小さいケースで試してみると、(0,1)と(1,1)のように1だけずれた点を同時に満たすロボットアームが構築できないことはすぐわかり、この考えを進めると、座標の(x+yの)偶奇がそろっている場合しかダメなことがわかる。
以下、偶奇がそろっている場合を考える。

整数点の座標は結構大きい値だが、腕の数が40程度のため、うまく長い腕と短い腕を組み合わせる必要がある。
そのような組み合わせとして(構築ゲーでよく出てくる)2冪の長さを考える。

m=1で、腕の長さが{1}の場合、以下のような到達点になる。

m=2で、腕の長さが{1,2}の場合、{1}の時の到達点を上下左右に2ずらしたところになるので、以下のような到達点となる。

したがって、{1,2,4,8,16,...}と2冪の長さで考えると、穴なくひし形範囲内のすべての点にたどり着けるようなロボットアームを構築できる。
上記はx+yが奇数の場合だが、偶数の場合は、{1,1,2,4,8,16,...}のように1を加えたものを考えればよい。

次に、整数点への関節の指定値の構築を考える。
これは、腕の長さが長いものから{2^30, 2^29, ... , 4, 2, 1}のようにしておき、原点からスタートして、上下左右の中で一番目的に近づくように設定するものを選んでいけばよい。

反省

• マンハッタン距離なので、x軸とy軸は独立に考えられそう
• 単純に半分に分けるとm=20程度で10^9を作らないといけないし、mをx軸とy軸でうまく分けたとしてもどっちも10^9程度の時に破たんしそう

みたいな考え方をしてしまって、単純に2冪だけでできる方向の考察ができなかった、、、