読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 414 Div1 Medium InfiniteSequence2

問題
  • i <= 0 の場合、A_i = 1
  • i >= 1 の場合、A_i = A_{\lfloor i/p \rfloor -x} + A_{\lfloor i/q \rfloor -y}

で定義される数列がある。\lfloor x \rfloorはxの床関数である。
A_nを返せ。

やりかた

単純なメモ化再帰で通る。ただしすべてメモするとMLEなので100万くらいまでメモっておいてそれ以上大きい場合は、再帰を繰り返して計算するようにすると通る。

以下ソース。

ll memo[1000001];

class InfiniteSequence2 {
public:
  int _p, _q, _x, _y;
  ll rec(ll idx){
    if(idx <= 0) return 1;
    if(idx <= 1000000 && memo[idx] >= 0) return memo[idx];

    ll ret = 0;
    ret = rec(idx / _p - _x) + rec(idx / _q - _y);
    if(idx <= 1000000) memo[idx] = ret;
    return ret;
  }
  long long calc(long long n, int p, int q, int x, int y) {
    _p = p, _q = q, _x = x,  _y = y;
    Fill(memo, -1);
    for(int i = 1; i <= 1000000; i++) rec(i);
    return rec(n);
  }
};

4,5,6月は忙しくてどれだけ解けるのか。SRMも全然出られてないし(´;ω;`)ブワッ

しょげないでよBaby 眠れば治る