yukicoder : No.1717 Levi-Civita Triangle

こちらはすんなり解けた。
https://yukicoder.me/problems/no/1717

問題

0,1,2からなる整数列Aを、以下のように長さが2短い新たな整数列f(A)にすることを考える。

• f(A)[i]は、(A[i],A[i+1],A[i+2])が：
  • (0,1,2)(1,2,0)(2,0,1)なら1
  • (0,2,1)(2,1,0)(1,0,2)なら2
  • それ以外なら0

整数列Aが与えられる。f(f(…f(A)…))と長さが1になるまでf(A)で置き換えた場合、残された値は何か。

解法

最終的な状態をBとし、その逆変換を考える。
逆変換が可能なのは、以下のケースのみである。

• 1 0 2 0 1 0 2 0 …
• 2 0 1 0 2 0 1 0 …

よって、B=[1]やB=[2]から逆変換でAが生成できるためには、f(A)が上記2パターンのいずれかでなければならない。
それ以外の場合はB=[0]となる。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N+1) {
		cin>>A[i];
	}
	FOR(i,2*N-1) {
		if((A[i]+1)%3==A[i+1]&&(A[i+1]+1)%3==A[i+2]) {
			B[i]=1;
		}
		if((A[i]+2)%3==A[i+1]&&(A[i+1]+2)%3==A[i+2]) {
			B[i]=2;
		}
	}
	N=2*N-1;
	FOR(i,N) {
		if(i%2==1) {
			if(B[i]) {
				cout<<0<<endl;
				return;
			}
		}
		else {
			if(B[i]==0) {
				cout<<0<<endl;
				return;
			}
			if(i&&B[i]==B[i+2]) {
				cout<<0<<endl;
				return;
			}
		}
	}
	x=B[0];
	while(N>1) {
		x=3^x;
		N-=2;
	}
	cout<<x<<endl;
}

まとめ

色々考えるなぁ…。