ABC235D

ABC235D の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc235/submissions/28827750

問題

初期値1にaをかけるか下一桁を先頭に移動させる（ただし桁数が変わってはならない）かのどちらかの操作を繰り返し行い，Nになるまでの最短の回数を考える問題です．

解説

幅優先探索で解くことができます．
数字を先頭に移動させる操作で桁数が変わらない制約のことを見落としていて，正解に辿りつくのに苦戦しました．

初期値1に操作を加えてNになる最短手数を考える問題ですが，
逆に，Nからスタートして，1になるまでの最短手数を考えようと思います．
Nから逆順に操作をするため，末尾を先頭に移動させる操作も逆になり，先頭を末尾に移動させる操作になりますので注意が必要です．

概要図です．

ABC235D_overview

幅優先探索の相棒のdequeのインポートと標準入力を読み込みます．

from collections import deque

a, N = map(int, input().split())

ここで，数字の先頭を末尾に移動させる操作を行う関数を定義します．この時桁数が変わらないように気をつける必要があります．桁数が変わったり，桁数が1で移動させる操作ができない時は，Noneをreturnするようにします．

def head_to_suffix(x):
    if x > 9 and x%10 > 0:
        s = str(x)
        if s[1] != '0':
            return int(s[1:] + s[0])
    return None

一度みた数字を再度探索することは無駄ですので，seenで管理して初めてみる数字のみ探索します．ansは最小手数が見つからないことを考慮して，-1で定義します．
dequeにはリストを入れるようにして，[現在の値, 現在の手数]で管理します．

seen = set([])
ans = -1
dq = deque([[N, 0]])

while文でBFSを行います．

すでにxが1であれば，これ以上の探索をする必要はありません．また幅優先探索なので，初めて1に到達した時の手数がそのまま最小手数になります．またelifですでに見た数字は探索しないようにします．初めての数字であれば，次から探索しないようにsetに加えておきます．

 次に２つの探索を行います．

1. 現在の値xをaで割りきれる場合は，aで割る．
2. 先頭を末尾に移動する操作ができる場合，すなわち上記の関数を実行して，return がNoneではないときは，その操作を行う．

操作をした値は，操作回数cntに+1をして，キューにappendします．

while dq:
    x, cnt = dq.popleft()
    if x == 1:
        ans = cnt
        break
    elif x in seen:
        continue
    else:
        seen.add(x)
    if x%a==0:
        dq.append([x//a, cnt+1])
    xh = head_to_suffix(x)
    if xh:
        dq.append([xh, cnt+1])

このwhile文のループを抜け出したとき，もし最小手数があればansはすでに更新されています．
あとはそのまま出力をすれば終了です．

print(ans)

以上，ABC235Dの解法でした．