AtCoder Beginner Contest 161 D

AtCoder Beginner Contest 161 D 問題を Python で解説していきます。私はルンルン数の作り方の仕組み自体は分かったのですが，それを解くプログラムが思いつかずにタイムアップしてしまいました。(´;ω;｀)
後の解説を見てキューを使えば上手くできることを知り，自分でプログラムを書いたので，それで解説していきたいと思います。
まずは問題から。

D – Lunlun Number

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

正の整数 X が以下の条件を満たすとき、 X はルンルン数であると言います。

X を(leading zeroなしで)十進数表記した際に、隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下

例えば、 1234 , 1 , 334 などはルンルン数ですが、 31415 , 119 , 13579 などはルンルン数ではありません。

正の整数 K が与えられます。小さい方から K 番目のルンルン数を求めてください。

制約

1≤K≤105
入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

K

出力

答えを出力せよ。

解説

実際に2桁までのルンルン数を列挙してみます。まずは一桁の整数である1~9まではルンルン数です。そして２桁のルンルン数は

10 11 | 21 22 23 | 32 33 34 | 43 44 45 | 54 55 56 | 65 66 67 | 76 77 78 | 87 88 89 | 98 99

のようになります。この二桁のルンルン数を一桁のルンルン数と紐づけて考えてみると，次のような法則性があることに気付くことができるのではないでしょうか。

N 桁のルンルン数 A の一の位が0の時
N+1桁のルンルン数を作ろうとすると，A*10 と A*10 + 1 が作れる
ex.) 1 -> 10 と 11
N 桁のルンルン数 X の一の位が1~8の時，一の位の数を B として
N+1桁のルンルン数を作ろうとすると，A*10 + (B-1) と A*10 + B と A*10 + (B+1) が作れる
ex.) 3 -> 32 と 33 と 34
N 桁のルンルン数 A の一の位が9の時
N+1桁のルンルン数を作ろうとすると，A*10 + 8 と A*10 + 9 が作れる
ex.)9 -> 98 と 99

この法則を三桁のルンルン数と二桁のルンルン数との間にも試してみてください。実際に成り立つことが分かると思います。このように，N 桁のルンルン数から N+1 桁のルンルン数が作れるわけです。
問題はこれをどのようにコードにするかです。

ここで，データ構造のキューを使えば，上手いことコードが書けます。(キューとは？というかたはこちらをご覧ください)要は，ルンルン数のデータを収納するようなリストを作成して，そのリストの一番下の値を取り出し，その値に応じた N+1 桁のルンルン数をリストの一番上に積んでいけば，ルンルン数を小さい順にリストに格納することができるわけです。

実際の動き　
L = [1, 2, 3, 4, 5, 6, 7, 8, 9] (ルンルン数のリスト)
L から 1 を取り出す。先ほどの法則1よりルンルン数10 と 11が作れる。リスト L にこの値を積む。
L = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

この操作をどんどん繰り返していって，K 番目のルンルン数が得られたときに操作をやめて出力すればいいです。

さて，最後は細かい動きの実装です。K 番目のルンルン数というのをどう表現するかですが，まず K が1~9までの時は，そのまま整数 1~9 に対応しますので，上記の操作をする必要はなく，K に対応する1~9の数字を出力します。

K が10以上の時を考えます。上記の操作をして，ルンルン数を１つ追加するごとに K の値を 1 小さくして，K の値が 0 以下になった段階で操作をとりやめ，K 番目のルンルン数を出力することを考えます。

まずはキューに1~9の数字を入れます。この時点でキューには 9 個の数字が入っているので，K から 9 を引きます。後は実際に K の値を具体的に考えて，操作を考えてみましょう。

例えば K = 13 の時
K -= 9 (K = 4 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 2 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = -1 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23]
出力したい 13 番目は 22 なので，L[-2]を出力

K = 14 の時
K -= 9 (K = 5 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 3 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = 0 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [3, 4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23]
出力したい 14 番目は 23 なので，L[-1]を出力

K = 15 の時
K -= 9 (K = 6 になる)
1 から 10，11 を作成。ルンルン数が二つできたので K -= 2 (K = 4 になる)
2 から 21，22，23 を作成。ルンルン数が三つできたので K -= 3 (K = 1 になる)
3 から 32，33，34 を作成。ルンルン数が三つできたので K -= 3 (K = -2 になる)
K < 0 なので操作を終了。この時点でルンルン数のリスト L に格納されているルンルン数は
L = [4, 5, 6, 7, 8, 9, 10, 11, 21, 22, 23, 32, 33, 34]
出力したい 15 番目は 32 なので，L[-3]を出力

以上が場合分けです。結局，最終的な K の値に応じて 3 パターンの場合分けを考えたらよいわけです。この場合分けが一般的に通じることを他の場合においても確かめてみてください。よって，実装すべき K の値による場合分けは以下のようになります。

最終的な K の値が -1 の時：L[-2] を出力
最終的な K の値が 0 の時：L[-1] を出力
最終的な K の値が -2 の時：L[-3] を出力

長くなりましたが，以上が解説になります。あとはこれをコーディングする作業ですね。
では，解答例を載せておきます。

解答例

from collections import deque
k = int(input())

q = deque([i for i in range(1, 10)])

# kが9以下ならその値を出力して終了
if k <= 9:
    print(k)
    quit()

k -= 9

# ルンルン数の法則から操作を行う
while k > 0:
    # aがキューから取り出した値
    a = q.popleft()
    # bがaの一の位の値
    b = a % 10
    if b == 0:
        q.append(10*a)
        q.append(10*a + 1)
        k -= 2
    elif b != 0 and b != 9:
        q.append(10*a + (b - 1))
        q.append(10*a + b)
        q.append(10*a + (b + 1))
        k -= 3
    else:
        q.append(10*a + 8)
        q.append(10*a + 9)
        k -= 2

if k == -1:
    print(q[-2])
elif k == 0:
    print(q[-1])
elif k == -2:
    print(q[-3])

かなり詳しく掘り下げて解説してみました。
法則性はなんとなく分かるんですが，それをコーディングするというのはちょっと難しかったですね。
キューを使うという発想が出れば簡単だったのかなと思います。
まだまだ精進しなければ！😔

もし分からないところがあったり，もっとこうした方がいいというものがあれば，ぜひコメントお願いします！
それでは！

タムログ

プログラミングについての情報発信をしていきます！

AtCoder Beginner Contest 161 D

問題文

制約

入力

出力

解説

解答例