概要
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配列は以下のようになっています。
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
1000000001
100000001
1000000010
1000000011
.
.
まあ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$！