Pythonで競プロに挑む日誌 vol.13 ~余剰は便利~

数学ガールを読んで, 高校生からやり直したい気分です.

現在の目標

• 今年の10月内に茶色を取得する
  • ABC の A, B 問題を全部解く←イマココ
• 年内に緑色を取得する
  • ABC の C, D 問題を全部解く
• APG4b で C++ にも手を出す

今日の問題

ABC006B - トリボナッチ数列

https://beta.atcoder.jp/contests/abc006/tasks/abc006_2

結果

answer1.py

#coding: utf-8
a, b, c = 0, 0, 1
n = int(input())

if n == 1:
    val = a
elif n == 2:
    val = b
elif n == 3:
    val = c
else:
    for i in range(4, n+1):
        val = a + b + c
        a = b
        b = c
        c = val

print(val % 10007)

# 実行時間：TLE(時間オーバー)
# メモリ　：- KB
# コード長：262 Byte
# 得点　　：0/100

実行時間 2sec 以内が実現できませんでした. いろいろ調べたところ, 10007 で割った "余り" がキーワードでした.

answer2.py

#coding: utf-8
a, b, c = 0, 0, 1

for i in range(int(input()) - 1):
    a, b, c = b, c, (a+b+c)%10007
    #a, b, c = b%10007, c%10007, (a+b+c)%10007 #この方がわかりやすい

print(a)

# 実行時間：278 ms
# メモリ　：2940 KB
# コード長：117 Byte
# 得点　　：100/100

「求める答えは余りなので, an を余りで更新していけばよい」, という考え方でした.

"10007 で割った余りを求める" という行為を考えると, 10007 の整数倍の塊に入れない数を求めることなのですから,

　　　「もとの数の和から求めた余り」=「余り同士の和から求めた余り」

となるわけですね（ややこしい...）

• https://mathtrain.jp/mod
• https://www.slideshare.net/chokudai/abc006
• https://yamakasa3.hatenablog.com/entry/2018/04/11/020718

今回学んだこと

• 余りって便利

明日やること

• ABC を解き続ける.