AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 161 D – Lunlun Number
下手に考えるとかなり厄介な問題で、愚直に下から求めていくのが簡単だと思われる。前回作成した数字を元にして、桁を一つ増やした次の数字を作成していくのがポイント。
# AtCoder Beginner Contest 161 D - Lunlun Number
# https://atcoder.jp/contests/abc161/tasks/abc161_d
# tag: キュー 愚直
# とりあえずどんな感じなのか、最初の方を手書きで列挙してみる
# 1, 2, 3, 4, 5, 6, 7, 8, 9,
# 10, 11, 12, 21, 22, 23, ...., 87, 88, 89, 98, 99,
# 100, 101, 110, 111, 112, 121, 122, 123...
# 例えば 1 -> (10, 11, 12) や 11 -> (110, 111, 112) といった
# 構造があり、桁数が一つ少ないものから、次の桁数のものを
# 順次構成することが可能。
# そこで、両端キュー(deque)を用いて、
# まず一桁の数 1 ～ 9 を中に入れておき、FIFOで順に取り出しながら
# 二桁の数を構成していき、それをキューに入れていく。
# 二桁の数が順番に出てきだしたら、そこから三桁の数を
# 構成し……とやれば、小さな数から順に取り出していける。
from collections import deque
def main():
K = int(input())
dq = deque(list(range(1, 10)))
cnt = 0
while cnt < K:
n = dq.popleft()
# 最後の桁が 0 以外なら、abc から abc(c-1)を作成し、キューに入れる
if n % 10 != 0:
dq.append(n * 10 + n % 10 - 1)
# abc から abcc を作成し、キューに入れる
dq.append(n * 10 + n % 10)
# 最後の桁が 9 以外なら、abc から abc(c+1)を作成し、キューに入れる
if n % 10 != 9:
dq.append(n * 10 + n % 10 + 1)
cnt += 1
print(n)
main()
関連
