【競プロ】[C++/TypeScript]B - Lucas Numberが解けない

はじめに
「B - Lucas Number」とは
間違った回答
C++での正しい回答
TypeScriptでの正しい回答
参考サイト

はじめに

競技プログラミングする前にC++の勉強しよ〜〜と思ってC++入門 AtCoder Programming Guide for beginners (APG4b)をやっていたんですが、その中で出題された「AtCoder Beginner Contest 079」の「B - Lucas Number」が解けない。。。。何度やっても実行時間制限超過(TLE)になり、不正解になってしまう。

「B - Lucas Number」とは

1 ~ 86番目のリュカ数を計算するソースコードを書きなさい。という問題になります。問題の詳細については、下記リンクを参照

atcoder.jp

間違った回答

TypeScriptで回答して、実行時間制限超過(TLE)になったあとTypeScriptよりも早い言語(C++)なら大丈夫かな？と思ってC++でも解いてみたんですが、どのみち実行時間制限超過(TLE)になりました。

TypeScriptでの回答

import * as fs from "fs";

const input = fs.readFileSync("/dev/stdin", "utf8");
const a = +input;

console.log(lucasNumber(a));

function lucasNumber(n: number): number {
  if (n === 0) {
    return 2;
  } else if (n === 1) {
    return 1;
  } else {
    return lucasNumber(n - 1) + lucasNumber(n - 2);
  }
}

C++での回答

#include <iostream>
using namespace std;

int64_t lucas_number(int64_t n)
{
    if (n == 0)
    {
        return 2;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return lucas_number(n - 1) + lucas_number(n - 2);
    }
}

int main()
{
    // 整数の入力
    int64_t n;
    cin >> n;
    cout << lucas_number(n) << endl;
    return 0;
}

問題文を読んで、はは〜ん再帰だな？と思って再帰を使って解いてみたんですが、実行時間制限超過(TLE)で不正解に....

f:id:l08084:20200911215717p:plain — 2200msかかってTLEで不正解に

C++での正しい回答

再帰を使うのをやめて、配列を使うと、実行時間制限内で計算が完了して、正解になりました。

C++での回答

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 整数の入力
    int N;
    cin >> N;
    vector<int64_t> L(N + 1);

    if (N == 1)
    {
        L.at(N) = 1;
    }
    else
    {
        L.at(0) = 2;
        L.at(1) = 1;
        for (int i = 2; i <= N; i++)
        {
            L.at(i) = L.at(i - 1) + L.at(i - 2);
        }
    }
    cout << L.at(N) << endl;
    return 0;
}

86番目のリュカ数は、939587134549734843になるため、int型で表せる2147483647 を超えてしまいます。そのため、int型ではなくint64_t型を使用する必要があります。

f:id:l08084:20200913183424p:plain — 再帰をやめると実行時間が1/200くらいになって正解になった

TypeScriptでの正しい回答

TypeScriptでも再帰をやめると、実行時間制限以内に計算が終わるようになります。

import * as fs from "fs";

const input = fs.readFileSync("/dev/stdin", "utf8");
const N = +input;

const L: BigInt[] = Array(N + 1);

if (N === 1) {
  L[N] = BigInt(1);
} else {
  L[0] = BigInt(2);
  L[1] = BigInt(1);

  for (let i = 2; i <= N; i++) {
    L[i] = BigInt(L[i - 1]) + BigInt(L[i - 2]);
  }
}

console.log(String(L[N]));