kmjp's blog

競技プログラミング参加記です

yukicoder : No.614 壊れたキャンパス

少し手間取った。
https://yukicoder.me/problems/no/614

問題

N個の建物が並んでいる。
各建物はK階建てであり、内部は階段で縦に移動できる。

隣接する建物同士は、一部の階同士でつながっており、建物番号の増加する方向にのみ移動することができる。
この建物同士のつながりは、同じ階同士とは限らない。

1番目の建物のS階から、N番目の建物のT階まで移動するために必要な、階段の移動階数の最小値を求めよ。

解法

基本的にはDPで、単純に各建物同士をつなぐ通路において、そこまでの階段移動階数の最小値を求めればよい。
ただし愚直に総当たりすると、i番目と(i+1)番目、および(i+1)番目と(i+2)番目がともに通路の数が多い場合、計算量が通路数の2乗となりTLEする。

そこで、(移動階数+現在の階)および(移動階数-現在の階)のRMQを持つことで、

  • 直前の建物の移動で現在より低い階に来た場合
  • 直前の建物の移動で現在より高い階に来た場合

から次の通路に移動する移動階数の最小値を高速に計算することができる。

int N,M,K,S,T;
vector<pair<int,int>> V[202020];
ll from[202020];
ll to[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>S>>T;
	FOR(i,M) {
		cin>>x>>y>>j;
		V[x-1].push_back({y,j});
	}
	
	map<ll,ll> cur;
	cur[S]=0;
	
	FOR(i,N-1) {
		map<ll,ll> nex;
		vector<pair<ll,ll>> T;
		FORR(c,cur) T.push_back(c);
		if(T.empty()) break;
		FOR(j,T.size()-1) {
			T[j+1].second=min(T[j+1].second,T[j].second+T[j+1].first-T[j].first);
		}
		for(j=(int)T.size()-2;j>=0;j--) {
			T[j].second=min(T[j].second,T[j+1].second+T[j+1].first-T[j].first);
		}
		FORR(e,V[i]) {
			if(nex.count(e.second)==0) nex[e.second]=1LL<<50;
			x = lower_bound(ALL(T),make_pair((ll)e.first,0LL))-T.begin();
			if(x>=0 && x<T.size()) nex[e.second]=min(nex[e.second],T[x].second+abs(e.first-T[x].first));
			x++;
			if(x>=0 && x<T.size()) nex[e.second]=min(nex[e.second],T[x].second+abs(e.first-T[x].first));
			x--,x--;
			if(x>=0 && x<T.size()) nex[e.second]=min(nex[e.second],T[x].second+abs(e.first-T[x].first));
		}
		swap(cur,nex);
	}
	if(cur.empty()) {
		cout<<-1<<endl;
	}
	else {
		ll ret=1LL<<60;
		FORR(c,cur) ret=min(ret,c.second+abs(T-c.first));
		cout<<ret<<endl;
	}
}

まとめ

シンプルだけどちょっと悩む感じの問題。