yukicoder : No.675 ドットちゃんたち

これは割とすんなり。
https://yukicoder.me/problems/no/675

問題

二次元座標において、毎秒座標(Px,Py)に点が生成される。

1秒ごとに、その時点で存在する全点に以下のいずれかの形を取るクエリを適用する。

• X軸方向に指定された分だけ行移動する。
• Y軸方向に指定された分だけ平行移動する。
• 原点を中心に90度回転させる。

Q個のクエリが与えられる。
最初のクエリを始める直前に生成された点から、最後のクエリを行う前に生成された点まで、計Q個の生成点についてクエリ実行後の座標を答えよ。

解法

座標の平行移動と回転は、3*3の行列で表現でき、その合成も3*3行列となる。
よって各クエリを3*3行列で表しつつその累積積（？）を取り点の移動後の座標を特定しよう。

int N;
ll PX,PY;
int C[101010],D[101010];

const int MAT=3;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);v[0][0]=v[1][1]=v[2][2]=1;};}; //

Mat mulmat(Mat a,Mat b,int n=MAT) {
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
	}
	return r;
}

Mat M[101010];

Mat hoge(int c,int d) {
	Mat m;
	if(c==1) {
		m.v[0][2]=d;
	}
	if(c==2) {
		m.v[1][2]=d;
	}
	if(c==3) {
		m.v[0][0]=m.v[1][1]=0;
		m.v[0][1]=1;
		m.v[1][0]=-1;
	}
	return m;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>PX>>PY;
	FOR(i,N) {
		cin>>C[i];
		if(C[i]!=3) cin>>D[i];
	}
	
	for(i=N-1;i>=0;i--) {
		M[i]=mulmat(M[i+1],hoge(C[i],D[i]));
	}
	FOR(i,N) {
		cout<<(M[i].v[0][0]*PX+M[i].v[0][1]*PY+M[i].v[0][2])<<" "<<(M[i].v[1][0]*PX+M[i].v[1][1]*PY+M[i].v[1][2])<<endl;
	}
}

まとめ

まぁこれは定番かな。