AtCoder ABC161 D - Lunlun Number

AtCoderに取り組んだ際のメモです。
問題ページはこちらです。

Point: 400
Difficulty: 982

ABC161は3完でした。レートは少し下がりました。

コンテスト中に考えたこと

・1桁の場合は、隣の桁がないのですべてOK (1,2,3,4,5,6,7,8,9 の9個）
・2桁の場合は、10の位の数に対して選択可能な1の位の数が決まる
　-> 10の位が1ならば、1の位に選べるのは 0, 1, 2 のいずれか
・3桁の場合も、同様に10の位の数に対して選択可能な1の位の数が決まる
・4桁以上の場合も同様

という感じで列挙していけそうな気がしたのですが、実装できず。。。
2桁の数字を列挙する際に、列挙済みの1桁の数字を使いたい。3桁の数字を列挙する際に、列挙済みの2桁の数字を使いたい。と考えたのですが、どのように保持しておき、取り出せばいいのかでつまづきました。

解説から学んだこと

キューを使って、条件を満たす数字を昇順に列挙する
・キューに 1, 2, 3, 4, 5, 6, 7, 8, 9 を投入する
・キューから一つ数字を取り出して、その数字を左にシフトして作れる数字をキューに投入する
　・例えば、1を取り出した場合は、10の位が1になり、1の位に使用可能な数は0, 1, 2 の3つなので、10, 11, 12をキューに投入する
　　-> キューの中身は {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} になる
・K回繰り返せば、解答となる数字が取り出せる

最下位の桁の数字を追加していくことで簡単に昇順に列挙できる
・自身で考えたときは、最上位の桁を変更していく形になっていた
・キューの中の最も小さい数字をとりだして、左にシフトし使用可能な数字を最下位に昇順になるようにつめる
・この手順を繰り返すことで、キューに投入される数字が昇順に並ぶことを保証できる

キューを適切に使っていて、これ以上ないくらいシンプルで。これが、コンテスト中に自分で思いつけるようになったら、楽しそうです。

条件に合う数字を昇順に列挙する際に、最上位ではなく最下位の数字を調整の対象とするのは、（解答を聞いたあとということもあるけれど）当たり前なことな気がします。

提出したコード（解説をもとに実装）

提出ページ

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var k int
	fmt.Fscan(r, &k)

	var q Queue
	for i := 1; i <= 9; i++ {
		q.push(i)
	}

	ans := 0
	for k > 0 {
		x, _ := q.pop()
		for i := -1; i <= 1; i++ {
			d := x%10 + i
			if d < 0 || d > 9 {
				continue
			}
			q.push(x*10 + d)
		}

		ans = x
		k--
	}
	fmt.Println(ans)
}

// Queue ...
type Queue []int

// pop ...
func (q *Queue) empty() bool {
	return len(*q) == 0
}

// push ...
func (q *Queue) push(i int) {
	*q = append(*q, i)
}

// pop ...
func (q *Queue) pop() (int, bool) {
	if q.empty() {
		return 0, false
	} else {
		res := (*q)[0]
		*q = (*q)[1:]
		return res, true
	}
}