yukicoder : No.2702 Nand Nor Matrix

これは実験ゲー？
https://yukicoder.me/problems/no/2702

問題

N*Nのバイナリ行列X(0)が与えられる。
ただしこの状態で1を取りえるのは1列目か1行目のみである。

時刻tの行列X(t)は、X(t-1)の状態により以下のように定まる。

• 1列目・1行目はX(t,r,c)=X(t-1,r,c)
• それ以外の場合：
  • X(t,r,c)=0なら、X(t-1,r,c)=nand(X(t-1,r-1,c),X(t-1,r,c-1))
  • X(t,r,c)=1なら、X(t-1,r,c)=nor(X(t-1,r-1,c),X(t-1,r,c-1))

T,R,Cが指定されるので、X(T,R,C)の値を答えよ。

解法

• X(0,0,1)!=X(0,1,0)の場合、2行目・2列目以降は0,1交互になる。
• X(0,0,1)==X(0,1,0)の場合、1行目のうち01が交互に並ぶのがC列目まで、1列目のうち01が交互に並ぶのがR行目までの場合、R行C列目が01市松模様状になり、その外側は01が交互に入れ替わる。

int N,Q;
int A[202020],B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) cin>>B[i+1];
	int miC=N;
	int miR=N;
	for(i=N-1;i>=2;i--) {
		if(A[i-1]==A[i]) miC=i;
		if(B[i-1]==B[i]) miR=i;
	}
	int d=0;
	if(A[1]==0&&B[1]==0) {
		d++;
		FOR(i,N) A[i]^=1, B[i]^=1;
		
	}
	
	
	cin>>Q;
	while(Q--) {
		ll T,R,C;
		cin>>T>>R>>C;
		R--,C--;
		if(R==0) {
			cout<<(d^A[C])<<endl;
		}
		else if(C==0) {
			cout<<(d^B[R])<<endl;
		}
		else {
			if(A[1]!=B[1]||T==0) {
				cout<<T%2<<endl;
			}
			else {
				T-=d;
				if(R<miR&&C<miC&&R+C-1<=T) {
					cout<<(((R+C)%2)^d)<<endl;
				}
				else {
					cout<<((T%2)^d)<<endl;
				}
			}
		}
	}
	
}

まとめ

考察だけで答え詰めるの難しそう。