CSAcademy Round #67 : F. Cyclic Shifts

思いつきそうで思いつかず。
https://csacademy.com/contest/round-67/task/cyclic-shifts/

問題

H*Wのグリッドが与えられる。
各マスには(1,1)～(H,W)までの整数ペアを1つずつ書く。
この時、以下を満たす配置が可能ならそれを求めよ。

• グリッド全体を右に何マスかローテートし、その後下に何マスかローテートする。その後、H*Wマスのうち少なくとも1つはr行c列に(r,c)が書かれた状態のものがある。

解法

まず解が生成できないケースは、H,Wの偶奇が一致しないケースである。
例えばH=1でWが偶数のときを考える。
題意を満たすには、0～(W-1)マスローテートすると一致する整数が1回ずつ登場しなければならない。
この時、この必要ローテート数の総和は奇数である。
一方、ローテートは偶置換の繰り返しなので、偶置換により必要ローテート数は2ずつしか変化しないので、全ての数値が一致する(c列に(1,c)が書かれる)状態にはできない。
行が偶数行あれば隣接行と帳尻合わせができるかもしれないが、奇数だと結局必要ローテート数が奇数になり不可。

さて、奇数p,qを用いてH=p*2^a、W=q*2^bと分解できたとする。
p*qのグリッドと(2^a)*(2^b)のグリッドを作り、掛け合わせることを考えよう。

以下各マス数のペアを書くのは面倒なので、row majorで0-indexに連番を振って考える。すなわちH*Wの行列における(r,c)→(r-1)*W+(c-1)とエンコードする。

• p*q (奇数×奇数)のグリッドの生成
  • 例えば1行7列の場合、"0123456"の状態が列と番号が一致した状態だが、"0415263"のように位置を2倍にすると、0～6個ローテートしたとき1個ずつ元の位置に戻るようにできる。
  • 縦も同様。よってまず各行上記のとおりシャッフルし、次に各列シャッフルする。
• (2^a)*(2^b)グリッドの生成
  • a==b==1のとき
    • (0,2)
    • (3,1)で良い。
  • a==1、b＞1のとき
    • (0,9,1,10,2,11,3,12)
    • (4,13,5,14,6,15,7,8) みたいにするとよい。
  • a＞1、b＞1のとき
    • a/2*b/2のグリッドを作り、2*2で4倍にする。その際、左上・右上・左下・右下の各(a/2*b/2)の大きさのグリッドは、(0,2)(3,1)の順で数字が大きくなるようにする。

int H,W;

pair<int,int> A[303][303],B[303][303],C[303][303];

void dfs(int H,int W) {
	int x,y;
	if(H==2 && W>2) {
		int cy=0,cx=0;
		FOR(x,W) {
			A[cy][cx]={0,x};
			cx+=2;
			if(cx>=W) cx%=W, cy^=1;
		}
		cy=1,cx=W-1;
		FOR(x,W) {
			A[cy][cx]={1,x};
			cx+=2;
			if(cx>=W) cx%=W, cy^=1;
		}
	}
	else if(H>2 && W==2) {
		int cy=0,cx=0;
		FOR(y,H) {
			A[cy][cx]={y,0};
			cy+=2;
			if(cy>=H) cy%=H, cx^=1;
		}
		cy=H-1,cx=1;
		FOR(y,H) {
			A[cy][cx]={y,1};
			cy+=2;
			if(cy>=H) cy%=H, cx^=1;
		}
	}
	else if(H>1 && W>1) {
		H/=2,W/=2;
		dfs(H,W);
		FOR(y,H) FOR(x,W) {
			A[y+H][x+W]={A[y][x].first,A[y][x].second+W};
			A[y+H][x]={A[y][x].first+H,A[y][x].second+W};
			A[y][x+W]={A[y][x].first+H,A[y][x].second};
		}
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>H>>W;
	
	if((H+W)%2==1) return _P("0\n");
	
	int X=1,Y=1;
	while(H%(Y*2)==0) Y*=2;
	while(W%(X*2)==0) X*=2;
	
	dfs(Y,X);
	int S=H/Y,T=W/X,s,t;
	FOR(s,S) FOR(t,T) B[s][t]={s,t};
	//yoko
	FOR(s,S) {
		vector<pair<int,int>> V;
		FOR(t,T) V.push_back(B[s][t]);
		FOR(t,T) B[s][t*2%T]=V[t];
	}
	//tate
	FOR(t,T) {
		vector<pair<int,int>> V;
		FOR(s,S) V.push_back(B[s][t]);
		FOR(s,S) B[s*2%S][t]=V[s];
	}
	
	FOR(s,S) FOR(t,T) {
		FOR(y,Y) FOR(x,X) {
			C[s*Y+y][t*X+x].first=A[y][x].first + B[s][t].first*Y;
			C[s*Y+y][t*X+x].second=A[y][x].second + B[s][t].second*X;
		}
	}
	_P("1\n");
	FOR(y,H) {
		FOR(x,W) _P("%d %d%c",1+C[y][x].first,1+C[y][x].second,(x==W-1)?'\n':' ');
	}
	
}

まとめ

説明がややこしいのでかなり省いてしまった。