AtCoder Beginner Contest 161 D - Lunlun Numberの考え方、Pythonでの解き方

※この記事はjohannyjm1さんに教えたもらった解き方を自分のために整理し直したものです。

元の問題

atcoder.jp

考え方

まず1 ~ 9までの数は必ずルンルン数となります。

次に1を取り出します。 ルンルン数の定義は「隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下」のため、 1に-1, 0, 1を加えた数字を繋げたものが次のルンルン数になります。

10,11,12の数字を最後に追加します。

2についても同様に行うと、下記のような状態になります。 問題文中の入力例１については、小さい方から 15 番目までのルンルン数を求める問題のため、答えは23であることが分かります。

この考え方では、最初に1 ~9の数字を順に見ていき、追加する数字を探索する順序を(-1,0,1)にすることで、数字の登場順がルンルン数の昇順になるようにしています。

取り出す数字が2桁である10になった場合を考えます。 10の下一桁である0に対して、-1, 0, 1の計算を行います。 この時、0から-1を引いた値は対象外となります。

これの繰り返しで解けるはずです。

上記は幅優先探索の考え方であり、queueに対しFIFO(First In First Out)を行うことで実装できます。 この

Pythonコード

※こちらのコードはjohannyjm1さんの下記提出のコードをベースにしています。

atcoder.jp

PythonでqueueのFIFOを実装するためには、dequeのappendとpopleftを用います。

コード上にコメントで説明を記載しています。

from collections import deque


def main():
    k = int(input())

    cnt = 9

    if k <= cnt:
        print(k)
        exit()

    q = deque(list(range(1, 10)))
    while len(q) > 0:
        # queueの一番左の値を出力
        v = q.popleft()

        for diff in (-1, 0, 1):
            # vから下一桁を取得するために%10を行う
            nv = v % 10 + diff

            # nvの値が0より小さい、もしくは10以上の場合は計算しない
            if nv < 0 or nv >= 10:
                continue

            # 例えば、1に2を繋げた12を出力したい場合、1(ここではv)に対し10をかける必要がある
            next_num = v * 10 + nv
            # queueの一番右の値を入力
            q.append(next_num)
            cnt += 1

            # 問題文で指定されたk回の数字を出力
            if cnt == k:
                print(next_num)
                exit()


if __name__ == "__main__":
    main()