ABC161 D - Lunlun Number

問題原文

atcoder.jp

問題要旨

10進表記において、隣り合う各桁の差の絶対値が１以下であるようなものを「ルンルン数」と呼ぶことにする。
番目のルンルン数を求めよ。

• 

解法

sample3が、 のときに3234566667だと言ってるので、最大でも10桁だということがわかる。
ので、10桁までルンルン数を全探索する。

想定はBFSっぽいことをしていて天才か〜？となった。

実装

実装だるそ〜とおもったけどそんなことはなかった。
実装に10分はかからんだろうということ、うまいやり方がぱっと出なかったら書いてしまった方が早そう。
itertoolsは偉大。

from itertools import product
K = int(input())

ans = []
for l in range(10):
    for s in range(1, 10):
        for pattern in product([-1, 0, 1], repeat=l):
            X = [s]
            for p in pattern:
                if not (0 <= X[-1] + p <= 9):
                    break
                X.append(X[-1] + p)
            else:
                ans.append(int(''.join(map(str, X))))

ans.sort()
print(ans[K - 1])

感想

まぁたまにはこういう力技もね。。。
ところでサンプルからヒントを見つけるのは想定ではないんですが、全国統一コンエキシビジョンで出た気がちょっとします。