kmjp's blog

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

AtCoder ABC #414 (ミラティブ プログラミングコンテスト2025) : G - AtCoder Express 4

ARC

細かいところが詰め切れず。
https://atcoder.jp/contests/abc414/tasks/abc414_g

問題

N個の駅が並んでおり、それぞれの座標が与えられる。
ここでM通りの列車が走っている。
各列車iは、l[i]～r[i]の駅のどこかで乗車し、L[i]～R[i]の駅のどこかで降車できる。その際、両区間は共通部分を持たない。
この列車に乗ったときの価格は、C[i]+(乗車していた距離)とする。

1番の駅から2～N番の駅に到達するのにかかる最小費用をそれぞれ求めよ。

解法

区間から区間に遷移したいので、SegTreeの要領で2^n区間に対し辺を張るテクを使おう。
これを使い、かかる値段をコストとしたグラフを考え、ダイクストラ法を利用する。

その際、区間をマージするような辺に対しては、最も右または最も左に移動するときに必要な距離の分だけコストにしよう。
そうすることで負のコストを払わなくて済む。

int N,M;
const int DI=17;
const int DI2=DI+1;
ll X[1<<DI];
ll L1[202020],R1[202020],L2[202020],R2[202020],C[202020];
int LV[19][4];

vector<pair<int,ll>> E[1<<22];
ll dp[1<<22];

void dfs(int tid,int lv,int L,int R,int x,int y,int id,int order,ll TX) {
	if(x>=R) return ;
	if(y<=L) return;
	int cur=LV[lv][tid]+(L>>lv);
	if(x<=L&&R<=y) {
		ll d=min(abs(TX-X[R-1]),abs(TX-X[L]));
		if(order==0) E[cur].push_back({id,d});
		else E[id].push_back({cur,d});
		return;
	}
	int M=(L+R)/2;
	dfs(tid,lv-1,L,M,x,y,id,order,TX);
	dfs(tid,lv-1,M,R,x,y,id,order,TX);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,1<<DI) X[i]=1LL<<60;
	FOR(i,N) cin>>X[i];
	//下側2通り
	FOR(j,1<<DI) {
		E[j].push_back({j+(1<<DI2),0LL});
		E[j].push_back({j+(2<<DI2),0LL});
		E[j+(3<<DI2)].push_back({j,0LL});
		E[j+(4<<DI2)].push_back({j,0LL});
	}
	
	int len=1<<DI;
	int cur=0;
	FOR(i,DI+1) {
		FOR(j,4) {
			LV[i][j]=cur+((j+1)<<DI2);
		}
		FOR(j,len/2) {
			E[(1<<DI2)+cur+j*2+0].push_back({(1<<DI2)+cur+len+j,X[((j*2+2)<<i)-1]-X[((j*2+1)<<i)-1]});
			E[(1<<DI2)+cur+j*2+1].push_back({(1<<DI2)+cur+len+j,0});
			E[(2<<DI2)+cur+j*2+0].push_back({(2<<DI2)+cur+len+j,0});
			E[(2<<DI2)+cur+j*2+1].push_back({(2<<DI2)+cur+len+j,X[(j*2+1)<<i]-X[(j*2)<<i]});
			E[(3<<DI2)+cur+len+j].push_back({(3<<DI2)+cur+j*2+0,0});
			E[(3<<DI2)+cur+len+j].push_back({(3<<DI2)+cur+j*2+1,X[(j*2+1)<<i]-X[(j*2)<<i]});
			E[(4<<DI2)+cur+len+j].push_back({(4<<DI2)+cur+j*2+0,X[((j*2+2)<<i)-1]-X[((j*2+1)<<i)-1]});
			E[(4<<DI2)+cur+len+j].push_back({(4<<DI2)+cur+j*2+1,0});
		}
		cur+=len;
		len/=2;
	}
	
	int id=5<<(DI2);
	FOR(i,M) {
		cin>>L1[i]>>R1[i]>>L2[i]>>R2[i]>>C[i];
		L1[i]--,L2[i]--,R1[i]--,R2[i]--;
		if(R1[i]<=L2[i]) {
			dfs(0,DI,0,1<<DI,L1[i],R1[i]+1,id,0,X[L2[i]]);
			dfs(2,DI,0,1<<DI,L2[i],R2[i]+1,id+1,1,X[L2[i]]);
		}
		else {
			dfs(1,DI,0,1<<DI,L1[i],R1[i]+1,id,0,X[R2[i]]);
			dfs(3,DI,0,1<<DI,L2[i],R2[i]+1,id+1,1,X[R2[i]]);
		}
		E[id].push_back({id+1,C[i]});
		id+=2;
	}
	priority_queue<pair<ll,int>> Q;
	FOR(i,id) dp[i]=1LL<<60;
	dp[0]=0;
	Q.push({-dp[0],0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(dp[cur]!=co) continue;
		FORR2(e,c,E[cur]) if(chmin(dp[e],co+c)) Q.push({-dp[e],e});
	}
	FOR(i,N-1) {
		if(dp[i+1]>=1LL<<60) dp[i+1]=-1;
		cout<<dp[i+1]<<" ";
	}
	cout<<endl;
	
	
}

まとめ

本番中区間に対し辺を張ることは思いついたが、コストが負の辺の解消法に思い至らなかった。