TopCoder SRM 512 Div1 Medium SubFibonacci

1発回答ではなかったけど、なんとか自力で解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11288

問題

distinctな整数列Sが与えられる。
フィボナッチ数列とは、3つ目以降の要素が手前2要素の和である整数列をいう(2要素以下の数列は必然的にフィボナッチ数列である)。

ここで、以下の処理を行う。

• 先手はあるフィボナッチ数列の部分列のうちSからなる要素だけからなるものを作成する。
• 後手も同様に部分列を作成する。
• 両者を連結して数列を1つ作成する。

最終的に作成される数列は昇順でなければならないとき、この数列の要素数を最大化せよ。

解法

まずフィボナッチ数列からどのような部分列の抽出の仕方ができるかを考える。
S[x]を初項とし、S[y]がz番目に来るようなフィボナッチ数列を考える。

A[0]=1, A[1]=0から生成するフィボナッチ数列A[i]と、B[0]=0、B[1]=1から生成するフィボナッチ数列B[i]を事前に準備しておく。
すると初項X[0]=p、2項目X[1]=qであるようなフィボナッチ数列はX[z]=p*A[z]+q*B[z]となる。
これより、p=S[x]、X[z]=S[y]とするとS[y] = S[x]*A[z] + q*B[z]より2項目qを求めることができる。

S[y]の位置zを1～50程度で総当たりして初項と2項目を求めることで、S中2要素以上を含むフィボナッチ数列を生成できる。
この手順でフィボナッチ数列を色々生成し、先手および後手が取れる部分列をbitmaskの形で列挙して行こう。

あとはこのbitmask集合より、最後の数列が昇順であるという条件から、S中l番目以前を先手、それ以降を後手がとるとしてbit数が最大となるように部分列を選択すればよい。

class SubFibonacci {
	public:
	int maxElements(vector <int> S) {
		int i,j,x,y,z,t;
		int lm[51],rm[51];
		ll A[101],B[101];
		
		A[0]=B[1]=1;
		A[1]=B[0]=0;
		for(i=2;i<50;i++) A[i]=A[i-1]+A[i-2], B[i]=B[i-1]+B[i-2];
		
		sort(S.begin(),S.end());
		if(S.size()<=4) return S.size();
		
		set<ll> SS;
		FOR(x,S.size()) for(y=x+1;y<S.size();y++) for(z=1;z<50;z++) {
			ll cur=S[y]-S[x]*A[z];
			if(cur<=0) continue;
			if(cur%B[z]) continue;
			ll tar=cur/B[z];
			ll mask=(1LL<<x)|(1LL<<y);
			t=x+1;
			for(j=1;j<50;j++) {
				ll val=S[x]*A[j]+tar*B[j];
				while(t<S.size() && S[t]<val) t++;
				if(t<S.size() && S[t]==val) mask |= 1LL<<t;
			}
			SS.insert(mask);
		}
		
		ZERO(lm); ZERO(rm);
		ITR(it,SS) {
			int tot=__builtin_popcountll(*it);
			x=0;
			FOR(i,S.size()) {
				x+=(*it&(1LL<<i))>0;
				lm[i]=max(lm[i],x);
				rm[i]=max(rm[i],tot-x);
			}
		}
		
		int ma=0;
		FOR(i,S.size()) ma=max(ma,lm[i]+rm[i]);
		
		return ma;
	}
};

まとめ

X[z]=p*A[z]+q*B[z]と置くことで初項・2項目・Z項目を簡単な式に落とし込む方式、今回たまたま思いついたけど今後も使えそうだ。