【ABC161 D】「Lunlun Number」を解く【Python3】

abc161d

コンテスト一覧へ

 

小さい方からK番目のルンルン数を求める問題です。

(ルンルン数とは、十進数表記した際に、隣り合うどの2つの桁の値についても、差の絶対値が1以下のものだそうです)

提出
import collections

k = int(input())

li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10

for i in range(1, n):
    a = q.popleft()
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    aa = a + str(num)
    st_li.append(aa)
    q.append(aa)
    count += 1
    if num != 9:
        aa = a + str(num+1)
        st_li.append(aa)
        q.append(aa)
        count += 1
    if count > k:
        print(st_li[k-1])
        exit(0)

この問題は、collectionsモジュールの「deque」を使用します。

これを使うことで、先頭の要素を取得・削除する際に、時間コストを少なくすることができます。

 

最初に文字列のリスト

li = [str(i) for i in range(1,10)]
# li = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

を作っておいて、先頭の文字列を取得・削除(popleft()を使用)します。

そして、取得した文字列の語尾の数字と誤差が1以内の数字を後ろにつけて、リストに加える、という操作を順番にやっていき、k番目にきたものが答えになります。

 

最初はqから「1」を取得し、後ろに「0」「1」「2」を足して、それぞれ「10」「11」「12」にしてから、qの最後に加えます。

他にも例えば、qの先頭に「21」があり、それを取得したときには、「210」「211」「212」をqの最後に加えることになります。

「st_li」には、ルンルン数が1から順番に入っている状態です。

「count」がk以上になったときに「st_li[k-1]」に入っているものが答えになります。

 

上記では文字列のリストを作って操作していますが、工夫すれば数字のリストでも同じことが可能です。

【ABC161】解説記事リスト

コンテスト一覧に戻る

コメントを残す

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