SRM687 div1 easy AlmostFibonacciKnapsack

考えたこと

• ナップザックDPの復元とか考えつつ問題文を読むと制約的に論外
• 上から貪欲にとっていくやつを考える
• 7とかが3+4でつくれるけど先に6を取っちゃうとだめ
• 漸化式の性質を何かうまく使う…？
• とりあえず漸化式の要素を順番に書いていってみるけどよくわからない
• 2,3,2+3-1,2+3*2-2,2*2+3*3-3,… で係数もフィボナッチ数列っぽくなってるけど何か使える気にならない
• i項目まででどういう数字をつくれるのかを実験する
• 3項目までで2～7がつくれる
• 4項目の6と合わせると8～13がつくれるので2～13がつくれる
• 5項目の9と合わせると11～22がつくれるので2～22がつくれる
• つくれない-1のケースが存在しない気がしてくる
• つくれる区間に穴が空いちゃうようなケースについてちゃんと考えてみるとなさそう
• 貪欲に上から取っていくような構成ができそう
• 最初に考えたように小さい方の数だと貪欲だとだめそうなのがある
• 4項目よりあとのだと貪欲で構成できそうなのでx>=6の間は貪欲に使ってよさそう
• 2～5は最初の3項の和で作れる
• 1をつくるのは a[i]+1 = a[i-1]+a[i-2] を利用して作れる
• 貪欲にやったら通った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class AlmostFibonacciKnapsack {
   public:
   vector <int> getIndices(long long x)
  {
    vector<ll> v;
    ll a=2, b=3;
    v.PB(a); v.PB(b);
    while(a+b-1 < 1e18) {
      ll tmp = b;
      b = a+b-1;
      a = tmp;
      v.PB(b);
    }

    vector<int> ans;
    ll idx = v.size()-1;
    while(x > 5 && idx >= 2) {
      if(x > v[idx]) {
        x -= v[idx];
        ans.PB(idx+1);
        // cout << x << endl;
      }
      idx--;
    }

    if(x == 5) {
      ans.PB(1); ans.PB(2);
    } else if(x == 4) {
      ans.PB(3);
    } else if(x == 3) {
      ans.PB(2);
    } else if(x == 2) {
      ans.PB(1);
    } else if(x == 1) {
      // ans.back() を消して ans.back()-1, ans.back()-2 を追加
      ll tmp = ans.back();
      ans.pop_back();
      ans.PB(tmp-1); ans.PB(tmp-2);
    }

    return ans;
  }
};