SRM678 Div1 Easy AlmostFibonacciKnapsack
問題
a[1] = 2, a[2] = 3, a[i] = a[i-1] + a[i-2] - 1 で作られる数列がある.整数 x が与えられるので, 数列に現れる数だけの和でx が表現できるか判定してください.
方針
easy : 2,3,4が構築出来るのは、数列に2,3,4が存在することから自明。 2 <= x < a[n] ならば、xが構築可能と仮定すると、 a[n]<=x<a[n+1] の時、 x-a[n] != 1 の時以外は x-a[n]が構築可能。
— まーす (@math) <a href=“https://twitter.com/math/status/718057820516519936”>April 7, 2016
@math もし x-a[n] == 1なら、 x-a[n-1] < a[n-1] かつ x' = x-a[n-1] > 1 なので、2 <= x' < a[n-1] の時に構築可能であることを使って、やっぱり構築可能
— まーす (@math) April 7, 2016
@math ということで、基本的に貪欲に大きい物を使っていくといい。x-a[n] == 1は例外
— まーす (@math) April 7, 2016
IDに_
を含む人のツイートを貼るとHTMLが崩れる
実装
class AlmostFibonacciKnapsack {
public:
vector<int> getIndices(ll x) {
vector<ll> a = { 2,3 };
while (a.back() <= x) {
a.push_back(a.back() + a.rbegin()[1] - 1);
}
a.pop_back();
vector<int> res;
for (int i = a.size() - 1; i >= 0; i--) {
if (x >= a[i] && x - a[i] != 1) {
x -= a[i];
res.push_back(i + 1);
}
}
return res;
}
};