幸いトップを取れました。
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の方が難しくない?