典型90【058 – Original Calculator（★4）】をpython解説

AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。

今回は、その内、の58問目である「Original Calculator（★4）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

問題名　【058 – Original Calculator（★4）】

入力

N, K

考察

・考えた内容の概要

この問題は、電卓に表示される数字の変化に周期性があることを利用して解くことができます。具体的には、一度表示された数字が再度表示されると、それ以降の数字の変化は周期的になります。

・考えたことの内容

1. 周期性の存在
   • 電卓に表示される数字は10⁵以下のため、同じ数字が2回以上表示される場合、その後の数字の変化は周期的になります。
   • この周期的な変化を利用して、K回の操作後の数字を効率的に求めることができます。
2. 周期の探索
   • ボタンAを押すたびに、表示される数字を記録していきます。
   • 同じ数字が2回表示された時点で、周期的な変化が始まることが確定します。
   • この時点での操作回数と、周期の大きさを求めることで、K回の操作後の数字を計算で求めることができます。

・実装した内容

Pythonのコードを用いて、上記の考察を実装しました。具体的には、ボタンAを押すたびに表示される数字を記録し、周期的な変化が始まるタイミングと周期の大きさを求めます。そして、これを基にK回の操作後の数字を計算しました。

手順

1. ボタンAを押すたびの数字の変化を記録
   • ボタンAを押すたびに、表示される数字をloopリストに記録します。
   • この時、すでに表示された数字が再度表示された場合、その時点での操作回数と周期の大きさを求めます。
2. K回の操作後の数字の計算
   • 周期的な変化が始まるタイミングと周期の大きさを基に、K回の操作後の数字を計算します。

この方法を用いることで、効率的にK回の操作後の数字を求めることができます。

コード

# 入力を受け取る
N, K = map(int, input().split())

# 既に表示された数字を記録するためのリスト
seen = [False] * 100000
# 表示される数字の変化を記録するリスト
loop = []
now = N
now = sum(map(int, str(now))) + now
now = now % 100000
cnt = 0

# K回の操作を行うか、既に表示された数字が再度表示されるまでのループ
while cnt < K and not seen[now]:
    cnt += 1
    # 既に表示された数字をTrueにする
    seen[now] = True
    # 表示される数字をloopリストに追加
    loop.append(now)
    # 次に表示される数字を計算
    next_num = sum(map(int, str(now))) + now
    now = next_num % 100000

# 最後の数字をloopリストに追加
loop.append(now)

# K回の操作が終了した場合
if K == cnt:
    print(loop[-2])
    exit()

# 周期的な変化が始まるタイミングを求める
head = loop.index(now)
# loopリストの最後のインデックス
tail = len(loop) - 1
# 周期の大きさを求める
loop_len = tail - head
# K回の操作後の数字を計算して出力
print(loop[(K - head - 1) % loop_len + head])

前の問題【056 – Lucky Bag（★5）】
次の問題【063 – Monochromatic Subgrid（★4）】