SRM 687 div1 easy:AlmostFibonacciKnapsack

問題

以下のような漸化式で数列が与えられる。

a[1] = 2
a[2] = 3
a[n] = a[n-1] + a[n-2] - 1

また, 2 以上 10^18 以下の整数 x が与えられる。各値が互いに異なる数列 b1, b2, ... を用いて x = a[b1] + a[b2] + ... + a[bn] としたい。このような {bi} が存在する場合はその数列のうち一つを求めよ。

解法

次のような戦略で x を構成することが出来ます。

• x==0 なら終了
• a[i] <= x < a[i+1] を満たす i を探す
• x==a[i]+1 なら, 数列 b に i-1, i-2 を追加して終了
• それ以外なら, x から a[i] を引いて, 数列 b に i を追加

これで上手く行くのは数学的帰納法で示せます。まず, x = 2, 3, 4 あたりで上の戦略が有効なのは明らかです。
x = 2, 3, ..., a[k]-1 まで上手く行くと仮定します。この時, x = a[k], a[k]+1, ..., a[k+1]-1 まで上手く行くことを示します。

x = a[k] は OK です。また, x-a[k] < a[k+1]-a[k] < a[k-1] より, x > a[k] の時は, b に k を追加して x-a[k] について考えれば上手く行くことがわかります。ただし, x==a[k]+1 の時だけは, 帰納法の仮定にないので, これは別に示さないとダメです。といってもこれも自明で, この時は x = a[k-1] + a[k-2] なので大勝利です。

const ll INF = 1e18+10;

class AlmostFibonacciKnapsack {
public:
    vector <int> getIndices(long long x) {
        vector<int> ans;
        if (x==1) {
            ans.push_back(-1);
            return ans;
        }
        vector<ll> arr;
        arr.push_back(2);
        arr.push_back(3);
        while (1) {
            int n = arr.size();
            ll tmp = arr[n-1] + arr[n-2] - 1;
            arr.push_back(tmp);
            if (tmp > INF) break;
        }
        int n = arr.size();
        while (x) {
            int i = 0;
            for (; i < n; i++) {
                if (arr[i] > x) break;
            }
            i--;
            if (arr[i]+1 == x) {
                ans.push_back(i-1);
                ans.push_back(i-2);
                break;
            }
            ans.push_back(i);
            x -= arr[i];
        }
        for (int& el : ans) el++;
        return ans;
    }
};