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;
    }
};