競技プログラミング

ABC161D Lunlun Number

問題

https://atcoder.jp/contests/abc161/tasks/abc161_d

方針

  • ルンルン数を、1番目から順に作成していきK番目のルンルン数を作成する

    ポイント

  • 1桁の自然数（1~9）は全てルンルン数である。
  • あるルンルン数Xが与えられた時、文字列Xの末尾に特定の文字を書き足すことで新たなルンルン数Yを作成することができる。
    • 書き足す文字の候補は、Xの末尾の文字をsとしてs-1, s, s+1である。
      • s=0の場合: s, s+1
      • s=9の場合: s-1, s
      • それ以外の場合: s-1, s, s+1
    • この時、明らかにX < Yである
    • 逆に、n>2として、あるn桁のルンルン数Yがある時、Yの先頭からn-1桁をスライスした数Xもまたルンルン数である。
      • Yに対してXはただ一つのみ存在する

アルゴリズム

上記の性質を使うと、

  1. 1~9が格納されたキューを用意する
  2. デキューする。その数から新たなルンルン数を2または3個作成、エンキューする。このステップを繰り返す。

ことで、K番目のルンルン数を得ることができる。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import queue
q = queue.Queue()
for i in range(1,10):
    q.put(i)
K = int(input())
for k in range(K):
    x =q.get()
    last = x % 10
    if last != 0:
        q.put(10*x + last - 1)
    q.put(10*x + last)
    if last != 9:
        q.put(10*x + last + 1)
print (x)

記事情報

  • 投稿日：2020年4月5日
  • 最終更新日：2020年4月5日