yukicoder : No.362 門松ナンバー

想定解とはちょっと違うけど。
http://yukicoder.me/problems/1010

問題

門松ナンバーとは、３桁以上の数であり、かつ各桁の整数を並べた列において連続する３要素が門松列を成すものを言う。
小さい方からK番目の門松ナンバーを答えよ。

解法

想定解は二分探索だが、自分は別解法で解いた。
f(x,y,d) := 全部でd桁、上２ケタがx,yであるような門松ナンバーの数
上記f(x,y,d)をまずDPで求める。
f([1-9],[0-9],d)の和を取ると、各桁における門松ナンバーの数がわかる。
そこからK番目の門松ナンバーが何桁あるか求め、合計門松ナンバー数がK個を超過しないような範囲で上の桁から順に値を決めていく。

int T;
ll K;
ll num[10][10][18];
ll dnum[18];
vector<int> cand[10][10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(x,10) FOR(y,10) FOR(r,10) {
		if(x!=r && ((max(x,r)<y)||(min(x,r)>y))) num[x][y][3]++, cand[x][y].push_back(r);
	}
	for(i=4;i<=17;i++) {
		FOR(x,10) FOR(y,10) FOR(r,10) {
			if(x!=r && ((max(x,r)<y)||(min(x,r)>y))) num[x][y][i] += num[y][r][i-1];
		}
	}
	
	for(i=3;i<=17;i++) {
		for(x=1;x<=9;x++) FOR(y,10) dnum[i]+=num[x][y][i];
	}
	
	cin>>T;
	while(T--) {
		cin>>K;
		int d;
		FOR(d,17) {
			if(K<=dnum[d]) break;
			K-=dnum[d];
		}
		for(x=1;x<=9;x++) FOR(y,10) {
			if(K<=num[x][y][d]) goto out;
			K-=num[x][y][d];
		}
		out:
		_P("%d",x);
		d--;
		while(d>=3) {
			FOR(r,10) if(x!=r && ((max(x,r)<y)||(min(x,r)>y))) {
				if(K<=num[y][r][d]) break;
				K-=num[y][r][d];
			}
			x=y;
			_P("%d",x);
			y=r;
			d--;
		}
		_P("%d%d\n",y,cand[x][y][K-1]);
	}
	
}

まとめ

タイトルを門松数じゃなく門松ナンバーにしたのはなぜだろう。