ARC103 D - Robot Arms

AtCoder Regular Contest
問題(言い換え)

n個の点が与えられ、i個目の座標は(x[i],y[i])である
事前に自然数mとm個の数値dを自由に決めることができる
その後原点からスタートし、以下の操作をm回繰り返す
i番目の操作: 上下左右どれかの方向にd[i]だけ移動する
各操作の方向は自由に決められる
方向をうまく決めることで最終的にn個の頂点全てに到達可能であるようなmとdの組み合わせが存在するか判定し、存在するならm、d、各点へ辿り着けるような方向の組み合わせの具体例を1つ示せ

1 <= n <= 1000
|x[i]|, |y[i]| <= 10^9

1 <= m <= 40
1 <= d[i] <= 10^12

解法

n個の点全ての x[i]+y[i] の偶奇が等しくない場合は明らかに答えが存在しない
以下これらは全て奇数であるとする (偶数の場合はdに1を足して各点を1ずらせば奇数の場合と一緒になる)

座標を45度回転すると、n個の各点は (x[i]+y[i], x[i]-y[i]) となり、各移動は
(d[i], 0), (-d[i], 0), (0, d[i]), (0, -d[i]) だったものが
(d[i], d[i]), (-d[i], -d[i]), (d[i], -d[i]), (-d[i], d[i]) となる
つまりx座標とy座標はそれぞれ独立して+d[i]か-d[i]だけ動かせる
あとはd[i]の符号をうまく調整して x[i]+y[i] も x[i]-y[i] も作れれば良い

実は |x| <= 10^9 の範囲なら、 m = 31, d = {1, 2, 4, 8, ..., 2^30} とすればd[i]の足し引きで任意の奇数が作れる
厳密な証明は解説pdfに書いてあるんだけどちょっと何言ってるかわからなかった
具体的にd[i]の符号をどう決めるかというと、作りたい数字を2進数表記で一番左のビットから右へ順に見ていき、今見ているビットが下からkビット目だとすると、
そのビットが1のとき) d[i]=2^kであるようなd[i]の符号は正にする
0のとき) d[i]=2^kであるようなd[i]の符号は正にし、右に連続する0のビットに対応するd[i]は全て負にする
これを繰り返せばいい
これは結局、dを降順に見ていき、(今の位置)＜x[i]ならd[i]を足し、そうでないならd[i]を引く、というのを貪欲に繰り返すことに対応する

言葉だと相当説明しにくいから実際に適当な2進数で試すのが良いと思う
001 = 100 - 011なんかを利用して帳尻を合わせる感じ

int n, tx, ty, x[1010], y[1010], p = -1;
vector<int> d;
string di = "LDUR";

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> tx >> ty;
		int t = (abs(tx) + abs(ty)) %2;
		if (p==-1) p = t;
		else if (p!=t) return cout << -1 << endl, 0;
		x[i] = tx+ty, y[i] = tx-ty;
	}
	for(int i=30; i>=0; i--) d.push_back(1<<i);
	if (p==0) d.push_back(1);
	cout << d.size() << endl;
	rep(i,d.size()) cout << d[i] << (i==d.size()-1 ? '\n' : ' ');
	rep(i,n) {
		string ans;
		tx = 0, ty = 0;
		each(j,d) {
			bool xd, yd;
			if (tx<x[i]) tx += j, xd = 1;
			else tx -= j, xd = 0;
			if (ty<y[i]) ty += j, yd = 1;
			else ty -= j, yd = 0;
			ans.push_back(di[xd*2+yd]);
		}
		cout << ans << endl;
	}
}

DのACが54人でEが398人ってやばくね
Dの方が難しく感じる人の方が圧倒的に多いと思うけど、Eの構築は個人差ありすぎるから700より低く付けられなくて、こっちは使う知識が典型すぎるから600点より高く付けられないってことかな