ABC006-B - トリボナッチ数列 を解く(2)

ABC006-B - トリボナッチ数列 を解く(1) の続き

提出したコードは MLE になってしまった

なんで MLE になったんだっけ？

for i in range(3,n):
  l[i]=l[i-3]+l[i-2]+l[i-1]

 

そうだった

こんな調子でリストに馬鹿でかい数字をガンガン入れたから MLE になったんだ

 

考えてみるとリストに数字をいちいち保存する必要はないな

計算に必要な直前の3つの数字だけ残しておけばいいじゃん

 

提出したコード

# a1=0, a2=0, a3=1
a=0
b=0
c=1

# 入力
n=int(input())

# n=1,2,3 の場合
if n==1:
  print(a)
  exit()
elif n==2:
  print(b)
  exit()
elif n==3:
  print(c)
  exit()

x=0
for i in range(3,n):
  x=a+b+c

  # 次の計算の準備
  a=b
  b=c
  c=x

# n番目の項を10007で割った余りを出力
print(x%10007)

 

今回はリストを使ったやり方ではないから

n=1,2,3 のときは a1,a2,a3 をそのまま返すようにしておいた

これなら問題ないだろう

 

提出結果は TLE（制限時間超過）！！

今度は TLE か…

 

問題をよくみると n(1≦n≦10^6) なのでためしに 1000000 を入力して

手元で実行してみたら計算完了まで大分時間がかかった

手元で確認してから提出するべきだったな…

 

やはり終盤は数値が余りにも巨大すぎて

加算や代入ですら時間を要してしまうということなのだろうか？

 

うーん…どうしたものか…

 

ABC006-B - トリボナッチ数列 を解く(3) へ続く