TopCoder SRM 687 Div1 Easy AlmostFibonacciKnapsack

MediumでResubmitしたけど2Chalで辛うじてレート微増。
https://community.topcoder.com/stat?c=problem_statement&pm=14178

問題

以下のように定義される数列Aがある。

• A[1]=2
• A[2]=3
• A[i] = A[i-1] + A[i-2] - 1 (i≧3)

整数Xが与えられたとき、Aの部分列の和でXとなるものを答えよ。

解法

自分はX以下のAの要素について、大きい順で枝刈りDFSで要素を選択した。
「この要素は取っても取らなくても良い」というケースは余りなく、「これを取らないと以下の要素でXを達成できない」「これを取るとXを超えてしまう」というケースが多いため余り探索空間は広くならないようだ。
貪欲法で解くことも出来て、「A[i]を引いてもXが1にならないなら引く」を繰り返してもいいらしい。

ll A[200],S[200];

class AlmostFibonacciKnapsack {
	public:
	vector<int> ret,fin;
	
	void dfs(int cur,ll x) {
		if(fin.size()) return;
		if(x==0) {
			fin=ret;
			return;
		}
		if(cur<=0) return;
		if(x>S[cur]) return;
		if(x>=A[cur]) {
			ret.push_back(cur);
			dfs(cur-1,x-A[cur]);
			ret.pop_back();
		}
		if(fin.empty()) dfs(cur-1,x);
	}
	
	vector <int> getIndices(long long x) {
		int i;
		A[1]=2;
		A[2]=3;
		for(i=3;i<=86;i++) A[i]=A[i-1]+A[i-2]-1;
		for(i=1;i<=86;i++) S[i]=S[i-1]+A[i];
		
		fin.clear();
		ret.clear();
		dfs(86,x);
		if(fin.empty()) fin.push_back(-1);
		
		return fin;
	}
}

まとめ

あまり考えず枝刈り探索してしまった。