SRM 512 Div1 Medium SubFibonacci

TopCoder 探索

2時間以上色んな所でハマった。

問題

フィボナッチ数列とは、初項、第二項を除く項が、その直前と二つ前の項の和になっているような数列のことを言う。


正の整数の列Sに対して以下の操作を行う。

  • AshがSからフィボナッチ数列の（必ずしも連続しない）部分列を取る。順番はSの順に従う必要はない。
  • ElshがSの残りから同様の操作をする。
  • Ashの取った列とElshの取った列を、その順につなげる。

つなげた列は増加列になっていなければならないとき、
できる列の最大の長さはいくつであるか、求めよ。

制約条件

Sの項数≦50
Sの各項≦100000000
Sの各項は互いに異なる。

方針

問題文からは分かりにくいのだが、実は4, 2, 6, 8のような列を取ることはできない。
（4, 2, 6, 8が増加列になっていないため）
なんじゃそりゃって感じ。


Sをまずソートしておく。
ソート後のSの、i番目からj番目までからフィボナッチ数列の部分列を取るとき、最大でいくつ取れるかを求めてlen[i][j]とする。
すると、len[a][b]+len[c][d]の最大値が求める答えである。


len[i][j]を求めることを考える。
len[a][b]+len[c][d]は全てのa≦b＜c≦dを動くので、
S[i],S[j]は長さ最大の列に含まれるとしてよい。
（S[i],S[j]が入らず、i＜k≦l＜jを満たすようなS[k],S[l]が含まれるとき、len[k][l]にその場合が含まれるため）


S[i]をフィボナッチ数列のa番目、S[j]をフィボナッチ数列のb番目と決めつける。
フィボナッチ数列の初項をx,第二項をyとすると、
フィボナッチ数列はx, y, x+y, x+2y, 2x+3y, 3x+5y, ..., fib[i]x+fib[i+1]yとなるため、
（ただしここでfibは、fib[0]=1, fib[0]=0, fib[n]=fib[n-1]+fib[n-2]を満たす数列とする）
S[i]=fib[a]*x+fib[a+1]*y
S[j]=fib[b]*x+fib[b+1]*y
という連立方程式が立ち、x,yがそれぞれ求まる。


したがって、S[i]からS[j]までの数列に、このフィボナッチ数列の項が何個入っているかを全て調べることにより、len[i][j]を求めることができる。


fib[i]はi=40程度で1億を超すため、a,bは40くらいまで調べればいい。
i,jも最大で50通りずつくらいなので、全体で50^5回くらいのループしか回らないので以上の方法で間に合う。

ソースコード

int n,len[50][50];
ll f[55];

class SubFibonacci {
public:
  int maxElements(vector <int> S) {
  	n=S.size();
  	sort(S.begin(),S.end());
  	f[0]=1; f[1]=0;
  	rep(i,50)f[i+2]=f[i+1]+f[i];
  	
  	rep(i,n)rep(j,n)len[i][j]=i==j;
  	rep(j,n)rep(i,j){
  		
  		rep(a,40)rep(b,40)if(a!=b){
  			
  			int x,y;
  			ll p=f[b+1]*S[i]-f[a+1]*S[j],q=f[a]*f[b+1]-f[b]*f[a+1];
  			
  			x=p/q;
  			if(f[a+1])y=(S[i]-f[a]*x)/f[a+1];
  			else y=(S[j]-f[b]*x)/f[b+1];
  			
  			if(x<=0||y<=0)continue;
  			if(f[a]*x+f[a+1]*y!=S[i]||f[b]*x+f[b+1]*y!=S[j])continue;
  			
  			int s=i,t=0,k=40;
  			ll tmp[40];
  			bool big=0;
  			rep(c,40){
  				tmp[c]=f[c]*x+f[c+1]*y;
  				if(big||c&&tmp[c-1]>100000000)big=1, tmp[c]=100000000;
  			}
  			rep(c,k){
  				while(s<j&&tmp[c]>S[s])s++;
  				if(tmp[c]==S[s])s++,t++;
  				if(s>j)break;
  			}
  			len[i][j]=max(len[i][j],t);
  		}
  	}
  	
    int ans=0;
  	rep(j,n)rep(i,j+1)ans=max(ans,len[i][j]);
  	rep(d,n)rep(c,d+1)rep(b,c)rep(a,b+1)ans=max(ans,len[a][b]+len[c][d]);
    return ans;
  }
};