yukicoder : No.620 ぐるぐるぐるりん

うーむ。
https://yukicoder.me/problems/no/620

問題

時刻t=0で座標(1,0)にある点がある。
時刻tに(X(t),Y(t))にある点は、時刻t+1には以下の場所に移動する。

• X(t+1) = X(t) - Y(t)ω + X(t)v + U(x,t)
• Y(t+1) = Y(t) + X(t)ω + Y(t)v + U(y,t)

この点が、時刻Tの時点で座標(Gx,Gy)にいるようにしたい。
そのため、各時刻において、U(x,t)、U(y,t)は任意に設定できる。
ただし入力値Pに対しを満たさなければならない。
U(x,t)、U(y,t)をそれぞれどのように設定すればよいか一例を答えよ。

解法

Editorialは難しいし理解していないので、別の回答を参考にした。
なので
とおくと
となる。

よって、
を満たす範囲での総和を最小にする問題となる。
この式をベクトルUのコストと呼ぶことにすると、コストはベクトルの長さで決まり、回転させても変わらない。
また、そもそも行列Mは回転行列Rを整数s倍に拡大したものである。

とおけば
を満たすようU'を決める問題となる。
各U'にはsの累乗の重みを付けてコストの総和を取ることになるのだが、解説によると
のように配分するとコストの総和が最小となるようだ。

あとはU'からUを求めよう。

int N;
int T;
long double P,W,V,GX,GY;

pair<long double,long double> nex(pair<long double,long double> p,long double vx=0,long double vy=0) {
	long double x2=(1+V)*p.first-W*p.second+vx;
	long double y2=W*p.first+(1+V)*p.second+vy;
	return {x2,y2};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N--) {
		cin>>T>>P>>W>>V>>GX>>GY;
		
		pair<long double,long double> A[20];
		A[0]={1,0};
		FOR(i,T) A[i+1]=nex(A[i]);
		
		long double scale=sqrt((1+V)*(1+V)+W*W);
		long double co=(1+V)/scale;
		long double si=W/scale;
		
		if(scale<1e-10) {
			for(i=1;i<=T;i++) {
				if(i<T) _P("0 0\n");
				else _P("%lf %lf\n",(double)GX,(double)GY);
			}
			continue;
		}
		
		
		long double ssum=0;
		FOR(i,T) ssum+=pow(scale,2*i);
		long double cost=0;
		for(i=1;i<=T;i++) {
			long double vx=(GX-A[T].first)*pow(scale,T-i)/ssum;
			long double vy=(GY-A[T].second)*pow(scale,T-i)/ssum;
			FOR(j,T-i) {
				long double dx=vx,dy=vy;
				vx=co*dx+si*dy;
				vy=-si*dx+co*dy;
			}
			
			_P("%.15lf %.15lf\n",(double)vx,(double)vy);
			A[i]=nex(A[i-1],vx,vy);
			cost+=(vx*vx+vy*vy);
			//_P("%.15lf %.15lf  : %.15lf\n",(double)A[i].first,(double)A[i].second,(double)(vx*vx+vy*vy));
		}
	}
	
}

まとめ

これは自力で解ける気しないな～。