ルンルン数を色々な解法で解く（二分探索桁DPもあるよ！）

#概要
　ABC161-D[「Lunlun Number」](https://atcoder.jp/contests/abc161/tasks/abc161_d)を色々な解法で解くことで各手法の理解を深めるという記事です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/08ae37ee-3212-601a-12b6-c2ca9114bb7f.png)

　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で組んでいきます。

　以下、私の実装です。

```c++
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`配列は以下のようになっています。

```c++
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
1000000001
100000001
1000000010
1000000011
.
.
```

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

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

#想定解

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

```c++
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)$とします）

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

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

　では、$f(N)$はどうやって求めればいいのでしょうか。これは桁DPという手法により計算できます。桁DPの解説は[ココ](https://qiita.com/hibit/items/79ec62c4b469fbd66761)。

　実装が以下になります。

```c++
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$！