B - トリボナッチ数列 | AtCoder Beginner Contest 006

B - トリボナッチ数列 | AtCoder Beginner Contest 006

解法

フィボナッチ数の3つ版．フィボナッチは人名だが項数が増えた版は冗談のような名付けになっている．
実装方法はフィボナッチと同じく再帰．愚直に計算すると$O(n!)$となってしまうが，再帰関数の返り値をメモ化することで$O(n)$で求められる．

コーナーケース検討

10007で割った余りを出力する．

実装

配列は初期化子リスト{}で指定しなかった要素は0初期化されるので{}で全要素を0初期化出来る．また代入式はその代入される変数の変わりに使用できるのでtri()のreturn文は以下のように書ける．

#define MOD 10007
int memo[1000001] = {};//0-initialized
int tri(int n) {
    if (n <= 3 || memo[n] > 0) return memo[n];
    return memo[n] = (tri(n - 3) + tri(n - 2) + tri(n - 1))%MOD;
    // return memo[n] = (tri(n - 1) + tri(n - 2) + tri(n - 3))%MOD;
}
int main(int argc, char const *argv[])
{
    int n; cin >> n;
    memo[3] = 1;
    cout << tri(n) << endl;
    return 0;
}

Submission
上記のソースコードでコメントアウトしてある順で記述すると 上図のように実行速度，使用メモリ量ともに増加するのでtri(x)で出来るだけメモ化された値を再利用する(xが小さい順に計算される)ようにした方が効率がいい(この問題自体はどちらでもAC)．
Submission

データ構造・アルゴリズム

• 初期化
  • 配列
    • 初期化子{}
• 再帰
• メモ化
  • 初期化(今回は0初期化)
• 余り