blue_jamのTopCoder日記

SRM512 Div1 Medium を Analysis 読みながら解いてみた

SRM, Practice | 22:27

それは解いたとは言わない．

いつぞや参加したとき，一生懸命考えたけど解けなかったので，再び挑戦．

しかし，今回はanalysisという強力な味方（？）が．．．

概要

数列が与えられるので，任意のフィボナッチ数列(f[i] = f[i-1] + f[i-2]となるような数列)の部分列で構成された数列a, bを選ぶ．aとbを順に並べたときに，単調増加になるときのみ連結することができる．

連結した数列の最長の長さを求める．

解法

単調増加のときのみ連結できるので，並び替える．

与えられた数列を途中で2つに分ける．

小さいほうの数列，大きいほうの数列について，それぞれの要素で構成される最大のフィボナッチ数列の部分列の長さを計算，足し合わせる．

これをループを使って計算していって，最大値を解とする．

．．．とは言ったものの，フィボナッチ数列の部分列を計算できないと意味がない．

フィボナッチ数列の求め方

第0項a, 第1項bのフィボナッチ数列は，

a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, 8a+11b, ...

となる．

これを一般化すると，

第0項=a，第i項(i>=1)=fib(i-1)*a + fib(i)*b

(fib(i)は，fib(0)=0, fib(1)=1としたときのフィボナッチ数の第i項目)

が得られる．

第0項がaで，第d+1項がbのフィボナッチ数列があると仮定する．

このとき，第1項をcとすると，

b = a * fib(i) + fib(i+1) * c

となる1以上の整数が存在する．

式を変形すると，

c = (b - a * fib(i)) / fib(i+1) となり，第1項が求められる．

これから，フィボナッチ数列を生成していきながら，該当する数がいくつあるかカウントする．

すべてのa，b，dについて同様の処理を行い，そのうちの長さの最大値が，数列から得られるフィボナッチ数列の部分列の長さの最大値になる．

フィボナッチ数を探す際に，2分探索を用いてもよいし（Analysisはこちらのソースコードが載っている)，単調増加なことを利用して，前から順番に調べてもいい．

計算量は，数列の長さをNとするとO(N^5)．

O(N^4)の解法も存在する．Analysisの練習問題にあった．すべてのi(0<=i<N)について，iを上限として（下限として）含むフィボナッチ数列の長さを計算してから答えを計算する．実装が増えそうだったのでやっていない．</ppp>

ソースコード

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
define MAX 40
long long fib[41];
class SubFibonacci {
public:
	int solve(vector<int> &S, int low, int high){
		int res = 0;
		if(high - low < 3){
			return high - low;
		}
		for(int a=low; a<high; ++a){
			for(int b=a+1; b<high; ++b){
				for(int d=0; d <= MAX; ++d){
					long long t = S[b] - fib[d] * S[a];
					if(t <= 0 || t % fib[d+1] != 0)
						continue;
					int last = S[a];
					int curr = t / fib[d+1];
					int index = a + 1;
					int cnt = 1;

					while(curr <= S[high - 1]){
						int tmp;
						while(S[index] < curr && index < high)
							++index;
						if(index >= high)
							break;
						if(S[index] == curr)
							++cnt;
						tmp = last;
						last = curr;
						curr = last + tmp;
					}
					res = max(res, cnt);
				}
			}
		}
		return res;
	}
	int maxElements(vector <int> S) {
		int res;
		fib[0] = 0; fib[1] = 1;
		for(int i=2;i<=MAX;++i){
			fib[i] = fib[i-1] + fib[i-2];
		}
		res = 0;
		sort(S.begin(), S.end());
		int n = S.size();
		for(int i=0;i<=n;++i){
			res = max(res, solve(S, 0, i) + solve(S, i, n));
		}
		return res;
	}

};

フィボナッチ数は第39項目あたりで，与えられる数値の上限を超えます．

solve(S, low, high)は，low<=i<highとなるS[i]を用いた最大のフィボナッチ数列の部分列の長さを返します．</ppp>