これは何とか自力回答。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_4
問題
無限の長さを持つ1軸の数直線がある。
数直線上にN個のポイントA[i]がある。
現在位置をxとすると、1回のジャンプで任意のポイントに対称な位置2*A[i]-xに移動することができる。
Q個のクエリが与えられる。各クエリにおいて、座標S[i]からT[i]に移動する最小ジャンプ回数を求めよ。
解法
座標xにいるとき、ポイントA[i]とA[j]で2回ジャンプすると、2*A[j]-(2*A[i]-x) = x + 2*(A[j]-A[i]) に移動できる。
すなわち、2回ジャンプすると現在位置を問わず選んだポイントに応じて2*(A[j]-A[i])だけ移動できる。
まずはこの事実を用いて、距離0~20000までを移動するのに必要な最小ジャンプ回数を求める。
後は各クエリにおいて、以下の最小値を求めればよい。
- 前記2回単位の移動を利用してT[i]-S[i]だけ移動する最小ジャンプ回数を求める。
- 任意のポイントでまず1回(2*A[j]-S[i])に移動し、あとはそこから2回単位の移動で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); } }
まとめ
2回移動すると、元の位置と関係なく選んだポイントだけで移動量が決まる点に気づくとあとはすぐ。