yukicoder : No.1269 I hate Fibonacci Number

方針はすぐ浮かぶんだけどね。
https://yukicoder.me/problems/no/1269

問題

N桁の正整数のうち、その値を文字列とみなしたとき、その部分文字列として現れる数値にL以上R以下のフィボナッチ数が含まれないものを求めよ。

解法

L以上R以下のフィボナッチ数を列挙し、それらを文字列とみなしてAho-Corasickの遷移図を作ろう。
ノードが高々3桁個しかないので、N桁の各数字に0～9を取ったときの遷移を総当たりしていく。
「N桁の正整数」に0は許容されないので、最後に1を引くのを忘れないこと。

int N;
ll A[202020];
vector<ll> R[2];
void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N) R[A[i]%2].push_back(A[i]);
	
	ll ret=N;
	ll C[2]={},D[2]={};
	FOR(i,N) {
		x=A[i]%2;
		if(i&&A[i]==A[i-1]+1) {
			C[x]=max(C[x],D[x]+1);
			while(C[x]<R[x].size()&&R[x][C[x]]==R[x][C[x]-1]+2) C[x]++;
			ret+=C[x]-D[x];
		}
		D[x]++;
	}
	
	
	
	cout<<ret<<endl;
	
}

まとめ

フィボナッチ数があまりないことに気付けばすぐ。