他で余りでなさそうな問題。
https://yukicoder.me/problems/no/2010
問題
2次元座標上で、(0,0)-(X,H)の区間内を移動できるとき、(0,0)にある点を(X,0)まで移動させたい。
区間はY座標ごとにいくつかの領域に分かれており、各領域iでは点を距離1移動させるのに時間がA[i]かかる。
(X,0)まで移動させる場合の最短時間を求めよ。
解法
(0,0)→(X/2,*)→(X,0)と移動することを考える。前半と後半はx=X/2を対称軸として線対称となるように移動する。
ある区間iではX座標の横方向に移動するとする。この時、A[i]はA[0]~A[i]中で単独最小でなければならない。そうでなければ、A[i]に対応する領域を通る意味はない。
あとは、区間iを総当たりしよう。
スネルの法則を考えると、区間jでは偏角θに対しcosθ=A[i]/A[j]となるような角度で移動すると良い。
ただし、区間iに到達する前にX座標がX/2を超える場合は無視する。
int T,N; ll H[101],A[101]; double X; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>X; X/=2; FOR(i,N) cin>>H[i+1]; FOR(i,N) cin>>A[i]; double ret=A[0]*X; ll mi=A[0]; for(i=1;i<N;i++) { if(A[i]>=mi) continue; mi=min(mi,A[i]); double SX=0,tim=0; FOR(j,i) { double c=A[i]*1.0/A[j]; double s=sqrt(1-c*c); if(c==0) { tim+=(H[j+1]-H[j])*A[j]; } else { double t=s/c; SX+=(H[j+1]-H[j])/t; tim+=(H[j+1]-H[j])/s*A[j]; } } if(SX<=X) { tim+=(X-SX)*A[i]; ret=min(ret,tim); } } _P("%.12lf\n",ret*2); } }
まとめ
なるほど、スネルの法則をそう使うか…。