Codeforces #691 Div1 C. Latin Square

これは思いつかず…。
https://codeforces.com/contest/1458/problem/C

問題

N*Nのラテン方陣を成すマトリックスAが与えられる。
ここに命令列が与えられる。各命令では以下を行う。

• 1行上にシフトする
• 1行下にシフトする
• 1列右にシフトする
• 1列左にシフトする
• 各行について、順列を置換とみなし、その逆置換の順列に置き換える
• 各列について、順列を置換とみなし、その逆置換の順列に置き換える

最終的にマトリックスがどうなるかを答えよ。

解法

3次元座標上で、点(r,c,v)が存在する場合A[r][c]=vであることを意味するとする。
各命令は以下のように読み替えられる。

• rをインクリメントする
• rをデクリメントする
• cをインクリメントする
• cをデクリメントする
• Y座標とZ座標を入れ替える
• X座標とZ座標を入れ替える

命令列を実行すると、元座標のX,Y,Z座標がどの座標になるか、また各軸のインクリメント量・デクリメント量だけを計算しよう。
これは1命令O(1)で処理できる。
あとは、(r,c,A[r][c])が(r',c',v')に移動するなら、最終的なAはA[r'][c']=v'と置ける。

int T;
int N,M;
char S[101010];
int A[1010][1010];
int B[1010][1010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		FOR(y,N) FOR(x,N) scanf("%d",&A[y][x]), A[y][x]--;
		scanf("%s",S);
		int D[3]={};
		int V[3]={0,1,2};
		FOR(i,M) {
			if(S[i]=='R') D[1]++;
			if(S[i]=='L') D[1]--;
			if(S[i]=='U') D[0]--;
			if(S[i]=='D') D[0]++;
			if(S[i]=='I') swap(V[1],V[2]),swap(D[1],D[2]);
			if(S[i]=='C') swap(V[0],V[2]),swap(D[0],D[2]);
		}
		
		
		
		FOR(y,N) {
			FOR(x,N) {
				int C[3]={y,x,A[y][x]};
				int E[3]={C[V[0]]+D[0],C[V[1]]+D[1],C[V[2]]+D[2]};
				FOR(i,3) E[i]=(E[i]%N+N)%N;
				B[E[0]%N][E[1]%N]=E[2]%N;
			}
		}
		FOR(y,N) {
			FOR(x,N) _P("%d ",B[y][x]+1);
			_P("\n");
		}
		_P("\n");
	}
	
	
}

まとめ

置換を座標軸の入れ替えとみなすところに考えが至らず。
2次元で考えればそりゃそうか…。