kmjp's blog

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

CSAcademy Round #23 : D. Disk Mechanism

幸いトップを取れました。
https://csacademy.com/contest/round-23/#task/disk-mechanism

問題

1次元の数直線上に中心がある円盤がN個ある。
各円盤の中心座標はX[i]であり、円盤の半径はA[i]以上B[i]以下とする。
各円盤の半径が整数で、かつ隣接する円盤が互いに接するような配置は何通りあるか。

解法

円盤の半径がとりえる範囲を端から決めていこう。

i番の円盤を置いたとき、可能な半径がC[i]~D[i]とする。(A[i]≦C[i]≦D[i]≦B[i]となる)
この時、i番の円盤の右端は[X[i]+C[i],X[i]+D[i]]のため、(i+1)番の円盤がこれと接するためには半径が[X[i+1]-(X[i]+D[i]),X[i+1]-(X[i]+C[i])]でなければならない。
かつ、(i+1)番の円盤のとりえる半径は[A[i],B[i]]なので、実際は両者を満たす範囲は[X[i+1]-(X[i]+D[i]),X[i+1]-(X[i]+C[i])]と[A[i],B[i]]の共通部分である。
…という感じで0番から順に(N-1)番の円盤の半径の範囲を求めよう。

最終的に最後の円盤のとりえる半径の範囲が[C[N-1],D[N-1]]が存在するなら、(D[N-1]-C[N-1]+1)が解。

int N;
ll X[202020];
ll A[202020],B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N) cin>>A[i]>>B[i];
	
	ll L=X[0]+A[0],R=X[0]+B[0];
	for(i=1;i<N;i++) {
		ll TL=max(L,X[i]-B[i]);
		ll TR=min(R,X[i]-A[i]);
		if(TL>TR) return _P("0\n");
		
		L=2*X[i]-TR;
		R=2*X[i]-TL;
	}
	
	if(L>R) {
		cout<<0<<endl;
	}
	else {
		cout<<R-L+1<<endl;
	}
}

まとめ

これDよりCの方が難しくない?