AtCoder ABC 161 D - Lunlun Number 再帰関数 正解問題 long long

問題概要

1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。

K 番目に小さいルンルン数を求めよ。

制約

1≤K≤10^5

考えたこと

これはよくある再帰関数問題か..整数操作じゃなくて配列に整数を入れて後から文字列変換でどうにかなりそうだな。
0の時、9の時だけ注意してそれぞれ呼び出してあげれば完璧になりそうだな。
あれ？最後のほうの問題だけWAだ。あ、seisuu()の関数の戻り値がint型になってる！。これは怖いなー。注意ししないといけない。unsigned long long型に直して..　よし！ＡＣ！

こーど

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

long long X;
vector<long long> AllData;

unsigned long long seisuu(vector<long long> Data) {
	string Data_str = "";

	for (int num : Data) {
		Data_str += to_string(num);
	}
	unsigned long long Data_num = stoull(Data_str);
	return Data_num;
}

void lunlun(vector<long long> &Data) {//初期条件(1~9)

	//配列を整数に変換して、それが10~5以下のものなのかを判定する
	//整数をDataに入れる

	unsigned long long Data_num = seisuu(Data);
	if (Data_num < 5000000000) {
		AllData.push_back(Data_num);
	}
	else {
		return;
	}


	int Data_last = Data.back();//配列の最後の要素を取り出す
	//それぞれありうるルンルン数を配列に入れて呼び出す
	if (Data_last != 0) {
		Data.push_back(Data_last - 1);
		lunlun(Data);
		Data.pop_back();
	}

		Data.push_back(Data_last);
		lunlun(Data);
		Data.pop_back();

	if (Data_last != 9) {
		Data.push_back(Data_last + 1);
		lunlun(Data);
		Data.pop_back();
	}
}

int main() {
	cin >> X;
    vector<long long> Data;
	for (int i = 1; i < 10;i++) {
		Data.push_back(i);
		lunlun(Data);//1~9
		Data.pop_back();
	}

	//Data並び替え
	sort(AllData.begin(), AllData.end());

	cout << AllData[X - 1]<<endl;
}

ほかの人のコードを見てみた

参考にしたサイト
AtCoder ABC 161 D - Lunlun Number (緑色, 400 点) - けんちょんの競プロ精進記録

けんちょんさんのコード

#include <bits/stdc++.h>
using namespace std;

void rec(int d, long long val, vector<long long> &all) {
    // 格納
    all.push_back(val);

    // 10 桁だったらそれ以上やらずに打ち切り
    if (d == 10) return;

    // 次の桁へ進む処理
    for (int j = -1; j <= 1; ++j) {
        int add = (val % 10) + j;
        if (add >= 0 && add<= 9) rec(d+1, val*10+add, all);
    }
}

int main() {
    int K;
    cin >> K;
    vector<long long> all;
    for (int v = 1; v < 10; ++v) rec(1, v, all);

    // 小さい順に並び替える
    sort(all.begin(), all.end());

    // K 番目
    cout << all[K-1] << endl;
}

考えたこと

桁数を渡すやり方すげぇ。しかもこれ整数操作で解けるんだ。なるほどなぁ