【競技プログラミング】AtCoder Beginner Contest 006_B問題

問題

要約

1. トリボナッチ数列の定義

   • a₁ = 0
   • a₂ = 0
   • a₃ = 1
   • aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃ (n ≥ 4)

2. 数列の最初の8項
   0, 0, 1, 1, 2, 4, 7, 13

3. 求めるもの
   aₙ mod 10007 （aₙを10007で割った余り）

変数
n: 求めたい項の番号
aₙ: トリボナッチ数列の第n項

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

トリボナッチ数列は、直前の3項の和が次の項となる数列であり、初期値は0, 0, 1である。
大きな数値を扱う可能性があるため、各計算ステップで10007の剰余を取る

解法手順

1. 入力値nを整数として受け取る。
2. n+5の長さを持つリストaを0で初期化する。これは、インデックスのオーバーフローを防ぐためである。
3. トリボナッチ数列の初期値をセットする：a[0] = 0, a[1] = 0, a[2] = 1。
4. 3からn-1までのループを回し、各項を計算する。
5. 各項の計算では、直前の3項の和を求め、その結果を10007で割った余りを保存する。
6. ループ終了後、a[n-1]を出力する。これが求める解となる。

ACコード

ac.py

def io_func():
    # 入力値nを整数として受け取る
    n = int(input())
    return n

def solve(n):
    # n+5の長さを持つリストaを0で初期化する
    a = [0 for i in range(n+5)]
    
    # トリボナッチ数列の初期値をセットする
    a[0] = 0
    a[1] = 0
    a[2] = 1
    
    # 3からn-1までのループを回し、各項を計算する
    for i in range(3, n):
        # 直前の3項の和を求め、10007で割った余りを保存する
        a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10007
    
    # n番目の項（インデックスはn-1）を返す
    return a[n-1]

if __name__=="__main__":
    # メイン処理
    n = io_func()
    result = solve(n)
    print(result)

###
# n: 求めるトリボナッチ数列の項数
# a: トリボナッチ数列の値を保存するリスト
# i: ループカウンタ
# result: 計算結果（n番目のトリボナッチ数を10007で割った余り）

# 1. io_func関数:
#    - 標準入力から整数nを読み取る
# 2. solve関数:
#    - 引数nを受け取り、n番目のトリボナッチ数を10007で割った余りを計算する
#    - n+5の長さのリストaを0で初期化
#    - トリボナッチ数列の初期値（0, 0, 1）をセット
#    - 3からn-1までループを回し、各項を計算
#    - 各項は直前の3項の和を10007で割った余り
#    - n番目の項（a[n-1]）を返す
# 3. メイン処理:
#    - io_func関数で入力を受け取る
#    - solve関数で結果を計算
#    - 結果を出力