Wunder Fund Round 2016 : E. Robot Arm

方針は割とすぐ立ったけど、色々バグらせて時間切れ。
http://codeforces.com/contest/618/problem/E

問題

ある(N-1)個関節があるN個のセグメントをつないだ腕がある。
腕の根本は２次元座標上の原点にある。
初期状態は、各セグメントは1の長さを持ち、根本から順に右方向に連結している。

以下のクエリQ個が与えられるので、各クエリを適用したのちの先端部の位置を答えよ。

• あるセグメントの長さをz伸ばす
• ある関節を中心に腕をz回転させる。

解法

SegTreeの要領で、セグメントを倍々に連結していこう。
あるセグメントの根本から先端までの位置をP[i]、回転角度をD[i]とする。
セグメントを回転させるとその先のセグメントに回転の影響が与えられる。

よってセグメントi,jを連結したセグメントkは以下のように表現できる。

• D[k] = D[i] + D[j]
• P[k] = P[i] + (P[j]をD[i]度回転させた数値)

EditorialではDを角度でなく回転行列で持っているようだが、行列で乗算を繰り返すと誤差が心配なので角度で持っておいた方が無難。
幸い角度は度数法で整数だしね。

int NV=1<<19;
vector<pair<double,double>> pos;
vector<int> len;
vector<int> deg;
double pi;
int N,M;

pair<double,double> rot(pair<double,double> p,int d) {
	double c=cos(d/180.0*pi);
	double s=sin(d/180.0*pi);
	return {p.first*c-p.second*s,p.first*s+p.second*c};
}

void update(int entry, int L,int D) {
	len[entry]+=L;
	entry += NV;
	deg[entry]-=D;
	pos[entry]=rot({len[entry-NV],0},deg[entry]);
	
	while(entry>1) {
		entry>>=1;
		deg[entry]=deg[entry*2]+deg[entry*2+1];
		auto r=rot(pos[entry*2+1],deg[entry*2]);
		pos[entry]={r.first+pos[entry*2].first,r.second+pos[entry*2].second};
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	pi=atan(1)*4;
	len.resize(NV);
	pos.resize(NV*2);
	deg.resize(NV*2);
	
	cin>>N>>M;
	FOR(i,N) update(i,1,0);
	FOR(i,M) {
		cin>>j>>x>>y;
		if(j==1) update(x-1,y,0);
		if(j==2) update(x-1,0,y);
		_P("%.12lf %.12lf\n",pos[1].first,pos[1].second);
	}
}

まとめ

連結時の座標と角度を無駄に難しく考えすぎて間に合わなかった。
終わってみると非常に単純だ。