D – Lunlun Number 解説 (AtCoder Beginner Contest 161)

2020年4月4日AtCoder深さ優先探索, キュー, 全探索, 400点

問題へのリンク

問題概要

桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ

制約

  • \(1 \leq K \leq 10^5\)

考え方

制約が結構重要です。小さい方から1つずつ全探索することができれば、求められそうだということが分かります。

特殊な条件を持つ数を小さい方から全探索する時(パナソニックプログラミングコンテスト2020 D – String Equivalence など)は、深さ優先探索(DFS)を使うことは良くあり、今回もDFSで全探索することが可能です。

ただ、DFSでやると実装が面倒なので、思いつくなら公式解説にある通り Queue を利用するほうが簡単です。

解法1: DFS

DFS で小さい方の数から全探索します。

桁を固定して、小さい桁から探索するのがやりやすいと思います。

C++ での実装例

解法2: Queue

Queue を上手く利用すると簡単に全探索ができます。

先頭から取り出した値を一桁増やして最後尾に追加してやると、条件を満たす数が、順番に並びます。

取り出した数を n とすると、以下のように加えれば良いです。

  • n の 1 の位の数が 0 でないとき:n * 10 + (n % 10) – 1
  • すべての場合について:n * 10 + (n % 10)
  • n の 1 の位の数が 9 でないとき:n * 10 + (n % 10) + 1

これは幅優先探索(BFS)ということもできるでしょう。

C++ での実装例

サンプルに最大の時のケースがあるので、これを確認すると 64 bit 整数で収まることが分かります。実は string 型で保持する必要はないです。