POJ 2374: Fense Obstable Course

Tatsuya Yatagawa

2014-11-14

問題

ジョンの牧場はx座標が-1000000から1000000、y座標が0からNを取る整数座標と考えられる。各y=1…nについてx軸と平行な方向に柵が作られていて、i番目の柵はa[i]からb[i]まで続いている。ある牛は原点(0, 0)をスタートしてゴールである座標(s, n)に向かう。この時、牛は柵にぶつかるまではy軸方向に直進を続け、柵にぶつかったら左右どちらかに柵をよけるということを繰り返す。このとき、牛がゴールに到達するまでに歩かなければならない距離はいくつか？ただし、y軸方向の移動は考慮しなくてよい。

解法

DPです。ある柵iの両端に行くには、位置a[i]に最後に現れた柵の両端から移動してくるか、位置b[i]に最後に現れた柵の両端から移動してくるか、柵がその場所には表れていなくて、直接y座標が0の場所から歩いてくるかのどれかです。

なので、その中でどれが一番小さいかをdp表に記録しておいて、それを更新していってあげればよいです。ただ、ある位置xに最後に現れた柵を探す、という計算はbrute forceにやると、O(N)の時間がかかってしまうので、N = 50000であることを考えるとTLEになってしまいます。

結論から言うと、この最後に現れた柵の計算をセグメント木を使って高速化してあげます。クエリを処理するときは単純で、探索をしたい位置xを含むように全体の区間を半分半分にしていくだけです。当然計算量はO(logN)になります。

少し面倒なのは、a[i]からb[i]の位置をすべてiにするという処理です。一番単純には、その幅の分だけ、セグメント木の葉ノードを更新して、それに合わせて次々と親ノードを更新するという方法があります。が、当然ながらb[i]-a[i]はかなり大きい数なので、この更新処理では計算量がO(N)になり、これをN回繰り返さないといけないのでTLEです。

じゃあどうするかというと、セグメント木の各ノードが蓄える値を0に初期化しておいて、もし今更新しようとしている範囲が、セグメント木のノードの守備範囲に完全に内包されたら、そのノードの値を更新して探索を終了します。

そうしておくと、クエリを処理するときには葉ノードまでたどって戻ってくるまでの間の最大値をとれば、それが最後に必然的に最後に現れた柵の番号(今までで一番大きい)になります。

範囲の大小関係比較など実装でバグを出しやすそうですが、落ち着いてやれば多分解けます。この時かただと計算量はO(NlogN)です。試してはいないのですが、平方分割でやると計算量がO(N sqrt(N))なので、こっちだとかなりギリギリだと思います。

コード

// POJ 2374: Fence Obstacle Course
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(f,s) make_pair(f,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

const int OFFSET = 1000011;
const int SIZE = 1<<21;
int a[1000011];
int b[1000011];
int dp[2000022][2];
int seg[SIZE * 2];

void update(int val, int ql, int qr, int k, int l, int r) {
    if(ql == l && qr == r) {
        seg[k] = val;
        return;
    }

    int mid = (l + r) / 2;
    if(qr <= mid) {
        update(val, ql, qr, k*2+1, l, mid);
    }
    else if(mid <= ql) {
        update(val, ql, qr, k*2+2, mid, r);
    }
    else {
        update(val, ql, mid, k*2+1, l, mid);
        update(val, mid, qr, k*2+2, mid, r);
    }
}

int query(int p, int k, int l, int r) {
    if(l+1 == r) {
        return seg[k];
    }

    int mid = (l + r) / 2;
    int val = seg[k];
    if(p <= mid) {
        val = max(val, query(p, k*2+1, l, mid));
    } else {
        val = max(val, query(p, k*2+2, mid, r));
    }
    return max(val, seg[k]);
}

int calc(int i, int e) {
    return min(abs(a[i] - e) + dp[i][0], abs(b[i] - e) + dp[i][1]);  
}

void coding() {
    int n, s;
    scanf("%d %d", &n, &s);
    s += OFFSET;

    memset(seg, 0, sizeof(seg));
    memset(dp, 0, sizeof(dp));
    a[0] = b[0] = OFFSET;
    REPP(i,1,n) {
        scanf("%d %d", a+i, b+i);
        a[i] += OFFSET;
        b[i] += OFFSET;
        int l = query(a[i], 0, 0, SIZE);
        int r = query(b[i], 0, 0, SIZE);
        dp[i][0] = calc(l, a[i]);
        dp[i][1] = calc(r, b[i]);
        update(i, a[i], b[i], 0, 0, SIZE);
    }
    int ans = min(abs(s - a[n]) + dp[n][0], abs(s - b[n]) + dp[n][1]);
    printf("%dn", ans);
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cerr << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cerr << "This is local test" << endl;
    cerr << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}