概要

　ABC161-D「Lunlun Number」を色々な解法で解くことで各手法の理解を深めるという記事です。

　1,234みたいな各桁が1ずつ増えていく数字、または減っていく数字、変わらない数字、とにかく隣の桁の数字との差が1以下である数字をルンルン数と名付け、何番目かのルンルン数を計算する問題です。

DFS（幅優先探索）

　1ケタのルンルン数は1,2,3,4,5,6,7,8,9の9種類です。そこから10,11,12,21,22,23……と追加されていきますが、これらの数字の末尾だけ見れば、それから±1の数を右に足していけばよいので（ただし0と9の場合は注意が必要）、それをDFSで組んでいきます。

　以下、私の実装です。

vector<ll> ans(0);//dfsの値を保存するためのグローバル変数
 
void dfs(ll a){
  if(a > 3234566667) return;
  ans.push_back(a);
  int m = a%10;
  if(m > 0) dfs(10*a + m - 1);//0の時は-1は足せない
  dfs(10*a + m);
  if(m < 9) dfs(10*a + m + 1);//9の時は+1は足せない
}
 
int main(){
  int k;
  cin >> k;
  rep1(i,9) dfs(i);//1-indexed
  sort(ans);
  cout << ans[k-1] << endl;
}

　再帰のDFSで組んでいますが、何もなければ無限ループしてしまうので、停止条件が必要です。幸い、問題のサンプルコードで、10000番目のルンルン数が3234566667であることが示されているので、これを超えた時点でreturnすれば問題ないことがわかります。

　DFSによって埋められるans配列では、1の次は2ではなく10になっています。これは1でいける所までいった後でしか2を見ないというDFSの性質によるものであり、DFSが完了した後のans配列は以下のようになっています。

　まあsortすれば済む話ですが、もう少しスマートに解けそうです。

　ちなみに正解に要した最大計算時間は$7ms$でした。

想定解

　1の計算結果を追加、2の計算結果を追加、……、10の計算結果、11の計算結果、という風に値を追加できれば自然に配列は昇順となります。配列を使ってそれを実装していきます。（解説ではqueueを使っていますが、本質的な部分は同じです）

int main(){
  int k;
  cin >> k;
  vector<ll> ans(0);
  rep1(i,9) ans.push_back(i);//1-indexed
  for(int i=0;i<100000;i++){
    int m = ans[i]%10;
    if(m > 0) ans.push_back(10*ans[i] + m - 1);
    ans.push_back(10*ans[i] + m);
    if(m < 9) ans.push_back(10*ans[i] + m + 1);
  }
  cout << ans[k-1] << endl;
}

　正解に要した最大計算時間は$4ms$でした。ソートがない分高速になっているようです。

二分探索桁DP

　ここまでやる必要はないのですが、あえての桁DPです。

　まず、**「ある数Nにどれだけのルンルン数が含まれるのか？」**ということがわかれば（これを$f(N)$とします）

f(n-1)=k-1\\
f(n)=k\\

　となるような$n$を見つければ、それが求める答えになります。言い換えれば、$f(n)\geq k$を満たすような最小の$n$を見つけるということです。$f$は単調増加しているため、ある境目より左はすべて上の条件に対してFALSE、右はすべてTRUEになるはずなので、これは二分探索により効率的に絞り込むことができます。

　では、$f(N)$はどうやって求めればいいのでしょうか。これは桁DPという手法により計算できます。桁DPの解説はココ。

　実装が以下になります。

int main(){
  int k;
  cin >> k;
  //ここからにぶたん
  ll left = 0;
  ll right = 3234566668;
  while(left < right-1){
    ll mid = (left + right)/2;
    //ここから桁DP
    string s = to_string(mid);//文字列に変換
    int n = s.size();
    vector<int> digit(1,0);//桁を格納するための配列
    for(char c : s){//それぞれの桁の数を詰める
      int x = c - '0';
      digit.push_back(x);
    }
    int dp[n+1][10][2] = {0};
    rep1(j,digit[1]) dp[1][j][j<digit[1]] ++;
    rep1(i,n-1){//1-indexed
      rep(j,10){//0-indexed
        dp[i+1][j][1] += (j>0);
        for(int k=-1;k<=1;k++){
          int m = j+k;
          if(m == -1 || m == 10) continue;
          dp[i+1][j][1] += dp[i][m][1];
          dp[i+1][j][j<digit[i+1]] += dp[i][m][0]*(j<=digit[i+1]);
        }
      }
    }
    int sum = 0;
    rep(j,10) sum += dp[n][j][0] + dp[n][j][1];
    //ここまで桁DP
    if(sum < k) left = mid;
    if(sum >= k) right = mid;
  }
  //ここまでにぶたん
  cout << right << endl;
}

　正解に要した最大計算時間なんと$1ms$！