解けなかった. とりあえず式を書いてみれば良かったのかなあ.

問題

http://nyc2015.contest.atcoder.jp/tasks/nyc2015_4

方針

場所に依らず, a[i], a[j] を使ってジャンプすると, 距離 2 * (a[i] - a[j])) だけ移動できる.

偶数回のジャンプで右に d 移動する場合の cost[d] を幅優先探索で求めておく. 奇数回ジャンプの場合については, 最初に a[i] で 1 回移動してから偶数回ジャンプすると考える. クエリ処理の際に, a[i] について全数探索する.

解答

#define loop(n, i) for(int i=0;i<n;i++)
 
using namespace std;
const int INF = 1<<29;
const int MAX = 20010;
 
int main()
{
    int N; cin >> N;
    vector<int> a(N);
    loop (N, i) cin >> a[i];
 
    vector<int> cost(MAX+1, INF);
    cost[0] = 0;
 
    queue<int> q;
    q.push(0);
    while (q.size()) {
        int u = q.front();
        q.pop();
        loop (N, i) loop (N, j) {
            int v = u + 2*(a[i] - a[j]);
            if (v < 0 || v > MAX) continue;
            if (cost[v] > cost[u]+2) {
                cost[v] = cost[u]+2;
                q.push(v);
            }
        }
    }
 
    int Q; cin >> Q;
    while (Q--) {
        int s, t; cin >> s >> t;
        int ans = cost[abs(t-s)];
        for (int b : a) {
            ans = min(ans, cost[abs(2*b - s - t)] + 1);
        }
        cout << (ans < INF ? ans : -1) << endl;
    }
    return 0;
}