AtCoder Beginner Contest 161 D – Lunlun Number をPython3で解く

Share

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()
Share

コメントを残す

メールアドレスが公開されることはありません。