yukicoder : No.2455 Numbers Dictionary

これはすんなり。
https://yukicoder.me/problems/no/2455

問題

整数N,Kが与えられる。
1～Nの整数を、それぞれ文字列とみなし辞書順で並べたとき、Kは何番目に出てくるか。

解法

prefixがKより文字列順で小さいものを列挙しよう。
Kと比べ上から(n-1)桁は一致し、n桁目でKよりも小さくなるようなケースを、nとn桁目の値に対し総当たりしよう。

int T;
ll N;
string K;
ll p10[20];

ll hoge(ll N,ll v) {
	ll ret=0;
	int i;
	FOR(i,19) {
		if(N/p10[i]<v) break;
		if((v+1)*p10[i]>N) {
			ret+=N-v*p10[i]+1;
		}
		else {
			ret+=p10[i];
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,18) p10[i+1]=p10[i]*10;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		ll ret=0;
		FOR(i,K.size()) {
			ret++;
			FOR(j,K[i]-'0') {
				ll a=atoll(K.substr(0,i).c_str())*10+j;
				if(a>0) ret+=hoge(N,a);
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

最初間違えてK番目の値を求めてしまった。