天下一プログラマーコンテスト2014 予選B : C - 天下一王国の歴史

予選Bにも参加。相変わらず途中の問題でてこずって、Eを見もせず終了。
http://tenka1-2014-qualb.contest.atcoder.jp/tasks/tenka1_2014_qualB_c

問題

NxNのグリッドがあり、それぞれのセルは白または黒である。
あるグリッドの状態に対し、1つ時間が進むと各セルは隣接する黒マスの数が偶数なら白、奇数なら黒になる。
今、グリッドの状態が1つ与えられる。1つ前の時刻としてあり得るグリッドの状態を1つ答えよ。

なお、与えられるグリッドの状態に対し、最低1つは1つ前の時刻の状態が存在する。

解法

セルの色を白＝０、黒＝１と置くと、今のセルの状態をR[y][x]、次のセルの状態をC[y][x]として
C[y][x]=R[y-1][x]^R[y+1][x]^R[y][x+1]^R[y][x-1]
と表現できる。逆にこの問題ではCが与えられており、Rを求めたいので、上記式を変形すると
R[y+1][x]=C[y][x]^R[y-1][x]^R[y][x+1]^R[y][x-1]
となる。すなわち、y+1行目の状態はy行目から生成できる。

問題は、じゃあ最初の行はどう決めるの？ということだが、実は正方形であれば最初の行はどうであっても条件を満たす状態を作成できるので、最初の行は全部白とか全部黒とか適当に決め打ちすればよい。
この事実は公式解説のようにちゃんと証明もできるが、手元で何度か実験してもわかる。

void solve() {
	int f,i,j,k,l,x,y,mask;
	
	int N;
	string C[800],R[800];
	
	cin>>N;
	FOR(y,N) cin>>C[y];
	FOR(y,N) FOR(x,N) C[y][x]=C[y][x]=='#';
	FOR(y,N) R[y]=string(N,0);
	for(y=1;y<N;y++) FOR(x,N) R[y][x]=C[y-1][x]^(x>0&&R[y-1][x-1])^(x<N-1&&R[y-1][x+1])^(y>1&&R[y-2][x]);
	
	FOR(y,N) {
		FOR(x,N) _P(R[y][x]?"#":".");
		_P("\n");
	}
	return;
}

まとめ

最初の行が何でもよい、と気づけるかどうかがカギ。