yukicoder : No.1056 2D Lamps

考察は大変だけど、実装は簡単な問題。
https://yukicoder.me/problems/no/1056

問題

N*N2次元グリッド上の各セルに電球がついている。
以下の処理をそれぞれ任意回数行い、指定された2つのグリッドの間を状態遷移できるか求めよ。

• 1列のオンオフを切り替える
• 1行のオンオフを切り替える
• 斜め45度方向1列分のオンオフを切り替える

解法

各セルの状態を0(遷移前後でオンオフが同じ)/1(異なる)の2値で考える。
処理を行い全要素が0になるようにできればよい。

2*2領域の状態のxorを考えると、列・行のオンオフ切り替えではこれらは変化しない。
また、変化しない範囲で、グリッドの状態を任意に遷移できる。
そこで、斜め方向の処理を使い、2*2領域の取り方(N-1)*(N-1)通りのxorの値を全部0にできれば、後は行・列のクエリで全要素0にできる。

斜め方向の処理を使うと、この(N-1)*(N-1)通りのxorの値のうち、斜めの2ライン分が0/1切り替わる。
この処理を繰り返すと、1ライン分だけ0/1切り替えることができる。
この状態は、最初の行・列クエリで0/1切り替えていくのと似ている。
実際、この(N-1)*(N-1)通りのxorの値について、(y+1,x),(y-1,x),(y,x+1),(y,x-1)に位置する4つのxorの値を変えない範囲で任意の状態に遷移できる。
そこで、(N-1)*(N-1)通りのxorの値について、(y+1,x),(y-1,x),(y,x+1),(y,x-1)の値のxorが0であることをチェックすればよい。

int N,M;
char S[202][202][202];
int B[202][202];
int C[202][202];

int ok(int a,int b) {
	int y,x;
	FOR(y,N) FOR(x,N) B[y][x]=(S[a][y][x]=='#')^(S[b][y][x]=='#');
	FOR(y,N-1) FOR(x,N-1) C[y][x]=B[y][x]^B[y][x+1]^B[y+1][x]^B[y+1][x+1];
	for(y=1;y<N-2;y++) for(x=1;x<N-2;x++) if(C[y+1][x]^C[y][x+1]^C[y-1][x]^C[y][x-1]) return 0;
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,M) FOR(y,N) scanf("%s",S[i][y]);
	
	FOR(i,M-1) {
		for(j=i+1;j<M;j++) cout<<ok(i,j);
		cout<<endl;
	}
	
}

まとめ

言われてみると簡単だけど、本番一発で思いつくのは大変そう。