kmjp's blog

競技プログラミング参加記です

AtCoder ARC #103 : D - Robot Arms

途中離脱のためDEFはまともに考えられず。
https://beta.atcoder.jp/contests/arc103/tasks/arc103_b

問題

2次元座標において、N個の座標が与えられる。
ここで、M個の腕をそれをつなぐ(M-1)個の関節からなるアームを持つロボットを考える。
このアームは原点にいるロボットから生えており、間接毎に次の腕の向きを上下左右にできるものとする。

アームの先端がN個の座標すべてに到達できるようなアームの腕の長さを答えよ。

解法

まず前提として腕の向きをどうしても先端の座標のパリティは変わらないので、N個の座標のパリティが一致することは先に確認しておこう。
以下パリティが奇数の場合を考える。偶数の場合最後にの長さ1の腕を追加すればよい。

腕の長さを1,2,4,8,...とする。
実は2^0~2^kの腕があると、原点からマンハッタン距離が2^(k+1)-1以下のパリティが奇数の点はすべて到達できる。
よって、1,2,4,...,2^30ぐらいまで腕を準備すればよい。

腕の長い順に、腕の向きを指定した際に目的の座標とX座標またはY座標の差が最も広がらない向きに腕の向きを決めるとよい。

int N;
ll X[1001],Y[1001],P[1001];
ll M;
ll V[40];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		P[i]=(abs(X[i])+abs(Y[i]))%2;
		if(P[i]!=P[0]) return _P("-1\n");
	}
	
	M=32;
	FOR(i,32) {
		V[i]=1LL<<(31-i);
	}
	if(P[0]==0) V[M++]=1;
	
	cout<<M<<endl;
	FOR(i,M) {
		cout<<V[i]<<" ";
	}
	cout<<endl;
	
	FOR(i,N) {
		string S;
		FOR(j,M) {
			if(abs(X[i])>=abs(Y[i])) {
				if(X[i]>=0) {
					S+='R';
					X[i]-=V[j];
				}
				else {
					S+='L';
					X[i]+=V[j];
				}
			}
			else {
				if(Y[i]>=0) {
					S+='U';
					Y[i]-=V[j];
				}
				else {
					S+='D';
					Y[i]+=V[j];
				}
			}
		}
		cout<<S<<endl;
	}
}

まとめ

最初3の累乗でどうにかすることをも考えたけど、それでも解けるのかな。