More than 5 years have passed since last update.

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

Last updated at 2018-11-03Posted at 2018-09-20

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

現在の目標

今年の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 の整数倍の塊に入れない数を求めることなのですから,

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

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

今回学んだこと

余りって便利

#明日やること

ABC を解き続ける.

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up