World CodeSprint 8 : E. Decibinary Numbers

これもちょっと手間取ったが、定番テクで行ける。
https://www.hackerrank.com/contests/world-codesprint-8/challenges/decibinary-numbers

問題

通常２進数は各桁0か1の値をとり、10進数は0～9の値をとる。
10進数の整数を、無理やり２進数とみなすことを考える。
たとえば2016をこの方法で10進数で表現しなおすと2*8+0*4+1*2+6=24となる。

元々10進数の値Dについて、上記手法で表現しなおした値をf(D)とする。
f(D)を小さい順に並べたとき、x番目に来るような元のDを求めよ。
なお、f(D)=f(D')のときは、元の10進数表記で小さいほうの値が前に来る。

解法

xの上限は10^16である。この時、Dの最大値を求めてみよう。

以下の状態を考え、桁DPの要領でSをdの小さい順に求めていってみよう。
S(d, v) := d桁以下の整数pのうち、f(p)=vとなるものの数

f(10^19)=2^19となるが、f(p)=vとなるpの組み合わせを求めてみると、vが2^19未満となるpが10^16個以上ある。
よって解は10^19未満であることは明らかである。
S(19,v)を2分探索すると、x番目の値pに対するf(p)が求められる。
あとは辞書順x個目を求める定番テクとして、f(p)が等しくなる整数のうち解を上位の桁から決めていけばよい。

ll dp[21][300005];
ll sum[300005];
int Q;
ll X;
ll p10[22];

ll dfs(int d,ll K,int L) {
	ll ret=0;
	int i;
	if(d==0) return L;
	FOR(i,10) {
		if(K<=dp[d][L-(i<<d)]) {
			ret = p10[d]*i + dfs(d-1,K,L-(i<<d));
			break;
		}
		else {
			K -= dp[d][L-(i<<d)];
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dp[0][0]=1;
	int d;
	for(d=0;d<20;d++) FOR(x,300000) if(dp[d][x]) FOR(y,10) if(x+(y<<d)<300000) dp[d+1][x+(y<<d)] += dp[d][x];
	p10[0]=1;
	FOR(i,21) p10[i+1]=p10[i]*10;
	
	FOR(i,300000) sum[i]=(i?sum[i-1]:0)+dp[d][i];
	
	cin>>Q;
	while(Q--) {
		cin>>X;
		if(X==1) {
			cout<<0<<endl;
			continue;
		}
		x=lower_bound(sum,sum+300000,X)-sum;
		X-=sum[x-1];
		cout<<dfs(20,X,x)<<endl;
	}
	
}

まとめ

なんかHackerRankは微妙にテストケース数が多かったりなんか独特な印象。