ABC 161 D - Lunlun Number - sky’s 雑記

D問題というか緑レベルの問題にも慣れてきた感はあるんだけど、なかなか解ききるまでは至らずもう少し時間がかかりそう。

初手の方針

0から9までの数字で差の絶対値が1以下になるものをそれぞれvectorで定義する。あとはK回に達するまで列挙していけば良いなと思った。

vector<vector<ll>> v = {
    {0, 1},
    {0, 1, 2},
    {1, 2, 3},
    {2, 3, 4},
    {3, 4, 5},
    {4, 5, 6},
    {5, 6, 7},
    {6, 7, 8},
    {7, 8, 9},
    {8, 9}
  };

実装としては各桁をvectorで親子関係として保持しつつ上記の条件を満たすように数字を構築しようとした。例えば入力例1の場合15番目は上記vectorでは0,1,2,1,2,3となり2桁目が3と確定しそのときの1桁目の数値は上記vectorのindexである2なので結果23となるといった具合。が、問題があって例えば111と211のように1桁目と3桁目の関係まで遡って関係性を保持する方法が思い浮かばず本番では実装できなかった。

正答

Submission #11592080 - AtCoder Beginner Contest 161

方針はほとんど変わらずqueueを使うのが正答。

Kが1桁まではqueueに1から9までの数字をpushして2桁目以降は1桁目%10をindexとして上記vectorの値を参照する。新たにpushする値は 1桁目*10+v[1桁目%10][j] でありこの作業がK回に達した時点で終了として最終的にqueueの最後尾に入っている値が答えとなる。

振り返り

使用するデータ構造の勘所

n回繰り返す系はvectorやfor文だけでなくqueueやwhileの可能性を考える

これまでのD問題の傾向

最近グラフ系の問題が多かったのでDFSや再帰的な書き方を最初に試しがちだが、データ構造の選び方や数学（というかパズル）的な問題の捉え方もやはり重要なのでこの点留意する。