New Year Contest 2015 : D - ジャンプ

これは何とか自力回答。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_4

問題

無限の長さを持つ１軸の数直線がある。
数直線上にN個のポイントA[i]がある。
現在位置をxとすると、１回のジャンプで任意のポイントに対称な位置2*A[i]-xに移動することができる。

Q個のクエリが与えられる。各クエリにおいて、座標S[i]からT[i]に移動する最小ジャンプ回数を求めよ。

解法

座標xにいるとき、ポイントA[i]とA[j]で２回ジャンプすると、2*A[j]-(2*A[i]-x) = x + 2*(A[j]-A[i]) に移動できる。
すなわち、２回ジャンプすると現在位置を問わず選んだポイントに応じて2*(A[j]-A[i])だけ移動できる。
まずはこの事実を用いて、距離0～20000までを移動するのに必要な最小ジャンプ回数を求める。

後は各クエリにおいて、以下の最小値を求めればよい。

• 前記２回単位の移動を利用してT[i]-S[i]だけ移動する最小ジャンプ回数を求める。
• 任意のポイントでまず１回(2*A[j]-S[i])に移動し、あとはそこから２回単位の移動でT[i]に移動する最小ジャンプ回数を求める。

int N,Q;
int A[400];
int mi[20002];
set<int> S;
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(x,N) FOR(y,N) S.insert(2*(A[x]-A[y]));
	ITR(it,S) if(*it) V.push_back(*it);
	
	FOR(x,20001) mi[x]=1000000;
	mi[0]=0;
	queue<int> q;
	q.push(0);
	while(q.size()) {
		int k=q.front();
		q.pop();
		ITR(it,V) {
			x=k+*it;
			if(x>20000) break;
			if(x>=0 && mi[x]>mi[k]+2) mi[x]=mi[k]+2, q.push(x);
		}
	}
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		if(x>y) swap(x,y);
		
		if((y-x)%2) {
			_P("-1\n");
			continue;
		}
		int m=mi[y-x];
		FOR(i,N) {
			j=2*A[i]-x;
			m=min(m,1+mi[abs(y-j)]);
		}
		if(m>=100000) m=-1;
		_P("%d\n",m);
	}
}

まとめ

２回移動すると、元の位置と関係なく選んだポイントだけで移動量が決まる点に気づくとあとはすぐ。