JOI難易度７テンキー - あっとのTECH LOG

問題原文

問題要旨

みたなテンキーを考える。
最初カーソルが 0 においてあって、上下右左へ移動 or クリックで１回の操作と考える。
$M$ で割ったあまりが $R$ になるような数を入力するまで、最低何回の操作が必要か？

$1 \leq M \leq 10000$
$1 \leq R ＜ M$

解法

「時間いっぱい探索すればええやろ！w」と思ったけどやっぱり落ちた（まぁ流石にね）
状態の同一視を意識して考えると、
$dp[n\rbrack[x\rbrack :=$ カーソルが $n$ にあって、あまりが $x$ であるような状態にするための最小操作回数
がみえる。

更新順がえいってできる感じではないので、拡張ダイクストラみたいにやる。
実際は移動コストは１なのでBFSの拡張をするみたいにする。

実装

移動 + クリックをしたところに直接遷移すると、クリックしない場合とか同じマスでクリックする場合とか考えないといけなくなって面倒。
「キューから取り出した時にクリックする」ことにすれば、4方向の移動を考えるのが楽になる。

from collections import deque
M, R = map(int, input().split())
board = [
    [0, 1],
    [1, 0, 2, 4],
    [2, 1, 3, 5],
    [3, 2, 6],
    [4, 1, 5, 7],
    [5, 2, 4, 6, 8],
    [6, 3, 5, 9],
    [7, 4, 8],
    [8, 5, 7, 9],
    [9, 6, 8]
]

dp = [[float('inf')] * M for _ in range(10)]

dp[0][0] = 0
queue = deque([[0, 0]])  # 今いる場所, これまでのあまり
while queue:

    node, remainder = queue.pop()
    next_remainder = (10 * remainder + node) % M
    if dp[node][next_remainder] == float('inf'):
        dp[node][next_remainder] = dp[node][remainder] + 1
        queue.appendleft([node, next_remainder])

    for to in board[node]:
        if dp[to][remainder] != float('inf'):
            continue
        dp[to][remainder] = dp[node][remainder] + 1
        queue.appendleft([to, remainder])

print(min([dp[i][R] for i in range(10)]))

感想

拡張ダイクストラ的なの、先に実装を頭で詰め切ってからのほうが結局時間かからない気がする。