💯

【競プロ】特定文字列にするための操作回数を求めよ【Python3】

2025/06/01に公開

問題

s = input()[::-1]
bt = 0

for i in range(len(s)):
    abt = int(s[i]) - (bt % 10)
    if abt < 0:
        abt += 10
    bt += abt

print(len(s) + bt)

最初から分かっているのはAボタンの回数。どんな数字列だったとしても桁数の分だけAボタンは必ず押す。よって計算するのはBボタンの回数だけでよい。

print(len(s) + bt)
# bt：Bボタンを押した数

与えられた数字列に対して、入力者と逆の操作をする。右端から数字を小さくして0になったら取り除くという操作を行う。Aボタンの逆の処理をするボタンを逆Aボタンと呼ぶことにする。（Bも同様）

例）「21」だったとしたら

操作回数は4回。サンプルの出力例と一致する。

というわけで数字列を右から処理したいが、分かりづらいので数字列の方を逆転させることにする。

s = input()[::-1] ## ←これで入力文字列が逆転するよ

for i in range(len(s)):
    # ループの記述が簡単になる

# abt：その数字を0にするために逆Bボタンを押した回数
abt = int(s[i]) - (bt % 10)
    if abt < 0:
        abt += 10

数字が3だったら3回押す必要があるが、Bボタンは押すとすべての数字が変わってしまう。

1234 逆Bボタンを押す→ 0123

のでこれまでに押された回数から、s[i]が今いくつになっているのか計算する必要がある。
Bボタンは10回押すと1周回って同じ数字になるため、10で割った余りを使えばよい。

abt = int(s[i]) - (bt % 10)

こうすると例えばこれまでに計14回押した場合、4回押した場合と同じ状態となることを表現できる。
が、これだとabtがマイナスになった時、正常に計算できない。

abt = 2 - 4 = -2 ←おかしくなる

現在のループで2という数字を処理している時、ここまでに計4回ボタンを押していると実際には「8」になっているはずである。
このようにマイナスになった場合のみ10を足すと正しい数字に戻る。

# abt：その数字を0にするために逆Bボタンを押した回数
abt = int(s[i]) - (bt % 10)
    if abt < 0:
        abt += 10

同じ数字が続く時はBボタンを押す回数が節約できる。

11 → 操作回数：2回（Bボタンは1回だけ）

この場合には、ループの中の以下の部分では

# abt：その数字を0にするために逆Bボタンを押した回数
abt = int(s[i]) - (bt % 10)

最初の1の時は1回押したと計算されるが、2回目の1の時は0回となる。ゾロ目の場合、最初の数字の分だけBボタンを押す回数がカウントされ、2回目以降は0回。
ゾロ目でも例外処理を付け加える必要はない。

112 → 操作回数：14回（Bボタンは11回、Aボタンは3回）

これは2つに分けて考えられる。

112を取り除く操作回数＝99を取り除く操作回数＋2を取り除く操作回数

99とは2を取り除いた時点での残りの数字列の状態。11と同じように計算するとBボタンは9回、Aボタンは2回。よって

112を取り除く操作回数＝11＋3＝14回

つまりゾロ目＋他の数字といった場合でもループの中身はそのままでよい。

for i in range(len(s)):
    abt = int(s[i]) - (bt % 10)
    if abt < 0:
        abt += 10
    bt += abt

帰納法的なアレでどんな数字列でもこのコードで操作回数が割り出せることが分かる。（分かれ）