競プロ典型 90 問：058 - Original Calculator（★4）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/25
• 結果：解けた (でも、2,3問WAが出てデバッグに苦労した)
• 時間：1時間ぐらい

考えたこと

• ボタンAを押していく中で、過去に登場した数値が出てきたらあとは同じ。周期性を使って計算すれば良さそう。

公式解説

https://twitter.com/e869120/status/1400947432440008704

解説を読んだふりかえり

• 特に問題なかった。
• 2,3ケースだけWAが出ていて、40分ぐらいたったところで回答みた。方針はいいけど、単純に実装力の問題だった・・・。ソースや条件を整理し直してAC。

ソース

N, K = [int(x) for x in input().split()]

# ボタンAの操作の数字
def next(x):
    x2 = x
    y = 0
    while x2 != 0:
        y += (x2 % 10)
        x2 //= 10
    return (x + y) % (10**5)

# ループ検知のためのすでに登場した数値華道家のメモ
memo = [False] * (10**5 + 1)
# 登場した数値を保持
numlist = []
# ボタンAをK回押す。ただし、ループ検知したら抜ける。
x = N
for i in range(K+1):
    numlist.append(x)
    memo[x] = True
    x = next(x)
    # すでにある場合
    if memo[x]:
        break

if i<K:
    # breakで抜けてきたとき
    st_idx = numlist.index(x)
    # Wが周期
    W = len(numlist) - st_idx
    idx = (K - st_idx) % W
    ans = numlist[st_idx + idx]
else:
    # 周期性が無いときは、末尾でOK
    ans = numlist[-1]

print(ans)