WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM687 Div1 Easy "AlmostFibonacciKnapsack"

解法

A[i]の増加の仕方は2のべき乗ぐらいに凄く、A[90]ぐらいにはもうxの最大値である10^18を超える。
探索範囲は広くなさそうということで、枝刈り探索しました。

事後

Editorialを見ると、大きいものから順に貪欲に行けばいいらしい。
自分のやった枝刈り探索でも大きいものから順に試していったため、結果的にほぼベストなやり方となり、計算量が少なくなったようです。

ソースコード

const long long INF = -1;
bool ans[100];
bool ok;
bool work[100];
long long a[92];
long long s[92];

class AlmostFibonacciKnapsack {
    public:
    vector<int> getIndices(long long x) {
        // i番目の数値とi番目までの合計値を算出
        a[1] = 2;
        a[2] = 3;
        s[1] = 2;
        s[2] = 5;
        for (int i = 3; i <= 91; i++) {
            a[i] = a[i - 1] + a[i - 2] - 1;
            s[i] = s[i - 1] + a[i];
        }
        s[90] = s[91] = INF;

        // 枝刈り探索でいく
        for (int i = 1; i <= 91; i++) {
            work[i] = false;
        }
        ok = false;
        solve(91, x);

        // 答え設定
        vector<int> res;
        if (ok) {
            for (int i = 1; i <= 91; i++) {
                if (ans[i]) res.push_back(i);
            }
        } else {
            res.push_back(-1);
        }
        return res;
    }

    void solve(int cur, long long rem) {
        // 答えが確定していたら何もしない
        if (ok) return;

        // 残りが0になったら答え確定
        if (rem == 0) {
            ok = true;
            for (int i = 1; i <= 91; i++) {
                ans[i] = work[i];
            }
            return;
        }

        // indexが0になったらアウト
        if (cur == 0) {
            return;
        }

        // 合計値が少なくなってしまったらアウト
        if (s[cur] != INF && s[cur] < rem) {
            return;
        }

        if (a[cur] <= rem) {
            // 使う
            work[cur] = true;
            solve(cur - 1, rem - a[cur]);
            work[cur] = false;
        }

        // 使わない
        solve(cur - 1, rem);
    }
};