yukicoder : No.1268 Fruit Rush 2

なんだこのフィボナッチ推し。
https://yukicoder.me/problems/no/1268

問題

N個の正整数が与えられる。
i番目の要素は、A[i]番目のフィボナッチ数である。
また、各A[i]はことなる。

この正整数のうちいくつかを選んだとき、その和が再びフィボナッチ数であるような選び方は何通りか。

解法

1個だけ選ぶときは当然条件を満たす。
2個以上異なるフィボナッチ数を選ぶときは、F(x)をx番目のフィボナッチ数とすると

• F(x), F(x+1), F(x+3), F(x+5)...

と最初の2項だけ連続するフィボナッチ数で、それ以降2個飛びでフィボナッチ数を選んだ場合が相当する。

そこで、連続するフィボナッチ数が登場したら、尺取り法の要領で以降に続く2個飛びでフィボナッチ数が存在する区間を数え上げよう。

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;
	
}

まとめ

割と法則探すのに手間取った。