AtCoder ARC #108 : D - AB

アプローチを間違えた。
https://atcoder.jp/contests/arc108/tasks/arc108_d

問題

初期状態で"AB"という文字列がある。
この文字列を長さがNになるまで下記手続きを行う。

• 文字xとyがこの順で隣接している場所を選び、文字C[x][y]を挿入する。

最終的にあり得る文字列は何通りか。

解法

小さいNで実験すると、解は1か2^(N-3)かfib(N-1)になることがわかる。
以下では小さいNで実験してどのパターンかを見極めている。
厳密な分析はEditoral参照。

int N;
int C[2][2];
const ll mo=1000000007;

int ok(int v,int N) {
	if(N==2) return 1;
	for(int i=1;i<=N-2;i++) {
		int x=(v>>(i+1))&1;
		int y=(v>>(i-1))&1;
		int r=(v>>i)&1;
		
		if(C[x][y]==r) {
			int n=(v&((1<<i)-1)) | ((v>>(i+1))<<i);
			if(ok(n,N-1)) return 1;
		}
	}
	return 0;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,2) FOR(x,2) {
		cin>>s;
		C[y][x]=s[0]-'A';
	}
	if(N<=3) return _P("1\n");
	
	
	int mask;
	int num=0;
	FOR(mask,1<<(7)) {
		int v=(mask<<1)|1;
		if(ok(v,9)) {
			num++;
		}
	}
	
	if(num==1) {
		cout<<1<<endl;
	}
	else if(num==21) {
		ll F[1010]={};
		F[1]=F[2]=1;
		for(i=3;i<=1005;i++) F[i]=(F[i-1]+F[i-2])%mo;
		cout<<F[N-1]<<endl;
	}
	else if(num==64) {
		ll ret=1;
		FOR(i,N-3) ret=ret*2%mo;
		cout<<ret<<endl;
	}
	
}

まとめ

さっさと実験すればよかった。