ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。

memo[N] = 累計コスト+(木の高さ-現在位置)

このように持つと、正しくダイクストラ法により解を求めることが出来ます。

木の上下移動は最小限に抑える必要がありますが、木の距離から上下移動が必要かは簡単に調べることが出来るので、pushする前に上下移動が必要かどうかをその都度計算により調べます。

#include <bits/stdc++.h>
  
using namespace std;
  
#define ll long long
#define FOR(I,N) for(int I = 0;I<(int)(N);I++)
#define P pair<ll,ll>
#define pb push_back
#define INF 9223372036854775807
  
struct Node{
    vector<P> edges;
    int at;
    ll height;
    Node(int at_,ll height_){
        at = at_;
        height = height_;
    }
    Node(){}
};
  
vector<Node> ns;
  
int main(){
    int i,j;
    ll n,m,x,h,a,b,c;
    cin>>n>>m>>x;
    FOR(i,n){
        cin>>h;
        ns.pb(Node(i,h));
    }
    FOR(i,m){
        cin>>a>>b>>c;a--;b--;
        ns[a].edges.pb(P(b,c));
        ns[b].edges.pb(P(a,c));
    }
  
    ll memo[100001];
    fill_n(memo,100001,INF);
    priority_queue<P> que;
    vector<P> alp;
    alp.pb(P(0,x));
    que.push(P(-(ns[0].height-x),alp.size()-1));
    ll ans = INF;
    while(que.size()){
        P data = que.top();que.pop();
        P data2 = alp[data.second];
        ll cost = -data.first;
        int index = data2.first;
        ll tx = data2.second;
        if(memo[index]<=cost)continue;
        memo[index] = cost;
        if(index==n-1){
            ll tcost = cost-(ns[index].height-tx);
            ans = min(ans,tcost+ns[index].height-tx);
            ///break;
        }
  
        FOR(i,ns[index].edges.size()){
            int nind = ns[index].edges[i].first;
            ll distance = ns[index].edges[i].second;
            ll tcost = cost-(ns[index].height-tx);///本来のコスト
            ll ncost;
            ll nx;
            if(tx-distance<0){///移動後の位置がマイナスになる
                if(ns[index].height<tx+distance-tx)///高さ足りない
                    continue;
                ncost = tcost+distance-tx+distance+ns[nind].height-0;
                nx = 0;
            }else if(ns[nind].height<tx-distance){///移動後の位置が木の高さ超える
                ncost = tcost+(tx-distance)-ns[nind].height+distance+0;
                nx = ns[nind].height;
            }else{
                ncost = tcost+distance+ns[nind].height-(tx-distance);
                nx = tx-distance;
            }
            alp.pb(P(nind,nx));
            que.push(P(-ncost,alp.size()-1));
        }
    }
    if(ans==INF)ans=-1;
    cout<<ans<<endl;
    return 0;
}

2015-02-06

PCK2014予選「天体観測」

AOJに問題が登録されたので解いてみました。
AOJ0302

予め星の輝きをソートしておきます。
ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、
その様に選んだ時の長方形の面積Sの大きさは
S = (星座内で最も大きいX座標-最も小さいX座標)(最も大きいY座標-最も小さいY座標)
となり、これを高速に求めるためにRMQを用います。
全ての星に対してこの操作を行った時の最も大きい長方形の面積が解となります。

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define FOR(I,N) for(int I = 0;I<(int)(N);I++)
#define P pair<ll,ll>
#define pb push_back
#define INF 10000000000
 
vector<P> datas;
P sorted[200001];
ll sortedV[200001];
 
ll BSEG[1<<19][2];///x,y
ll MSEG[1<<19][2];///x,y
 
void updataB(int index,int t){
    if(index==0)return;
    int l = index*2,r = index*2+1;
    ll tmp = BSEG[index][t];
    if(BSEG[l][t]<BSEG[r][t]){
        BSEG[index][t] = BSEG[r][t];
    }else{
        BSEG[index][t] = BSEG[l][t];
    }
    if(BSEG[index][t]==tmp)return;
    updataB(index/2,t);
}
 
void updataM(int index,int t){
    if(index==0)return;
    int l = index*2,r = index*2+1;
    ll tmp = MSEG[index][t];
    if(MSEG[l][t]>MSEG[r][t]){
        MSEG[index][t] = MSEG[r][t];
    }else{
        MSEG[index][t] = MSEG[l][t];
    }
    if(MSEG[index][t]==tmp)return;
    updataM(index/2,t);
}
 
ll getMin(int a,int b,int k,int l,int r,int t){
    if(b<l||r<a)return INF;
    if(a<=l&&r<=b)return MSEG[k][t];
    ll lm = getMin(a,b,k*2,l,(r-l)/2+l,t);
    ll rm = getMin(a,b,k*2+1,(r-l)/2+l+1,r,t);
    return min(lm,rm);
}
 
ll getMax(int a,int b,int k,int l,int r,int t){
    if(b<l||r<a)return 0;
    if(a<=l&&r<=b)return BSEG[k][t];
    ll lm = getMax(a,b,k*2,l,(r-l)/2+l,t);
    ll rm = getMax(a,b,k*2+1,(r-l)/2+l+1,r,t);
    return max(lm,rm);
}
 
int main(){
    int i,j;
    ll n,d,x,y,c;
    cin>>n>>d;
    FOR(i,n){
        cin>>x>>y>>c;
        P data = P(x,y);
        datas.pb(data);
        sorted[i] = P(c,datas.size()-1);
        sortedV[i] = c;
    }
    sort(sorted,sorted+n);
    sort(sortedV,sortedV+n);
    int index = 1;
    while(index<n)index*=2;
    fill_n(*BSEG,(1<<19)*2,0);
    fill_n(*MSEG,(1<<19)*2,INF);
    FOR(i,n){
        P data = datas[sorted[i].second];
        x = data.first;
        y = data.second;
        BSEG[index+i][0] = x;
        MSEG[index+i][0] = x;
        BSEG[index+i][1] = y;
        MSEG[index+i][1] = y;
        updataB((index+i)/2,0);
        updataB((index+i)/2,1);
        updataM((index+i)/2,0);
        updataM((index+i)/2,1);
    }
    ll ans = 0;
    FOR(i,n){
        ll source = sorted[i].first;
        ll r = source+d;
        int li = i;
        int ri = upper_bound(sortedV,sortedV+n,r)-sortedV-1;
        if(li==ri)continue;
        ll sum = (getMax(li,ri,1,0,index-1,0)-getMin(li,ri,1,0,index-1,0))
        *(getMax(li,ri,1,0,index-1,1)-getMin(li,ri,1,0,index-1,1));
        ans = max(ans,sum);
    }
    cout<<ans<<endl;
     
    return 0;
}

2015-02-06

セグメントツリーメモ

更新は再帰的に処理します。各操作O(logN)

///RMQ
#define SIZE (1<<18)
#define ll long long
#define INF (1<<30)///必要に応じて増やす

ll int MSEG[SIZE];

void update(int index){
	if(index==0)return;
	int l = index*2,r = index*2+1,tmp = MSEG[index];
	if(MSEG[l]<MSEG[r]){
		MSEG[index] = MSEG[l];
	}else{
		MSEG[index] = MSEG[r];
	}
	if(tmp==MSEG[index])return;///更新が無ければ終了
	update(index/2);
}

ll getMin(int a,int b,int k,int l,int r){
	if(b<l||a>r)return INF;///含まない
	if(a<=l&&r<=b)return MSEG[k];///[a,b]が[l,r]を完全に含む
	ll ml = getMin(a,b,k*2,l,(r-l)/2+l);///左側
	ll mr = getMin(a,b,k*2+1,(r-l)/2+l+1,r);///右側
	return min(ml,mr);
}

hokekyo1210メモ

JOI2014本選「フクロモモンガ」

PCK2014予選「天体観測」

セグメントツリーメモ