Pythonで毎日AtCoder #43

はじめに

前回

#43

問題

考えたこと
コンテスト中に解けませんでした。この問題が難しいのはルンルン数を生成するコードを書けないからだと思います。私も書けませんでした。解説によると、10と9で割った余りに着目するようです。$x$を10で割った余りが0の時は一の位は0になり、生成可能なルンルン数は減ります。同様に$x$を9で割った余りが0の時も生成可能なルンルン数は減ります。なぜなら、一の位が0のとき隣合う数の差が1になるようなルンルン数は0、1しかありません。9のときも8、9しかありません。
それぞれどういったルンルン数を生成するかを整理すると、

x != 0 mod(10) → 10x+(x%10)-1
x != 9 mod(10) → 10x+(x%10)+1 

となります。これを実装すると

from collections import deque

k = int(input())

lun = deque([])
for i in range(1,10):
    lun.append(i)

for i in range(k):
    x = lun.popleft()
    if x % 10 != 0:
        lun.append(10*x+(x%10)-1)
    lun.append(10*x+x%10)
    if x % 10 != 9:
        lun.append(10*x+(x%10)+1)
print(x)

データの両端にしかアクセスしないので、dequeを使っています

まとめ

本番に解きたかった。余りを使った計算が苦手なので整数問題周りを練習します。ではまた。