Codeforces #426 Div1 C. Ever-Hungry Krakozyabra

手間取ったけど最終的には解けたのでまぁよかったか。
http://codeforces.com/contest/833/problem/C

問題

非負整数xに対するinedible tailとは、xの各桁を昇順に並べ替え、leading zeroを取り外したものである。
L,Rが与えらえるので、[L,R]の範囲の整数のinedible tailは何通りあるか答えよ。

解法

[L,R]の範囲で条件を満たすものを答える問題ではf(R)-f(L-1)を求めることが多いが、この問題は珍しく異なる。
まず、inedible tailの候補、すなわち18桁の整数で各桁昇順になっているものが何通りあるか考えよう。
これはH(10,18)なので4686824通りとさほど多くない。

よって、inedible tailの各候補Cに対し、[L,R]の範囲にCが存在しうるかを上の桁から順に見ていけばよい。
この判定はO(D) (Dは桁数)なので、inedible tailを総当たりしても間に合う。

ll L,R;
string LS,RS;
int D[10];
int ret,pat;
string A0,A9;

int hoge(int d,string& L,string& R) {
	if(d==L.size()) return 1;
	int ret=0;
	
	
	if(L[d]==R[d]) {
		if(D[L[d]]) {
			D[L[d]]--;
			ret=hoge(d+1,L,R);
			D[L[d]]++;
		}
		return ret;
	}
	int x;
	for(x=L[d]+1;x<R[d];x++) {
		if(D[x]) return 1;
	}
	if(D[L[d]]) {
		D[L[d]]--;
		ret |= hoge(d+1,L,A9);
		D[L[d]]++;
		if(ret) return 1;
	}
	if(D[R[d]]) {
		D[R[d]]--;
		ret |= hoge(d+1,A0,R);
		D[R[d]]++;
	}
	return ret;
}


int hoge() {
	pat++;
	D[0]++;
	if(D[0]!=19) ret+=hoge(0,LS,RS);
	D[0]--;
}

void dfs(int cur,int left) {
	if(cur==10) {
		if(left==0) hoge();
		return;
	}
	int i;
	FOR(i,left+1) {
		D[cur]=i;
		dfs(cur+1,left-i);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>LS>>RS;
	while(LS.size()<19) LS="0"+LS;
	while(RS.size()<19) RS="0"+RS;
	FORR(c,LS) c-='0';
	FORR(c,RS) c-='0';
	A0=string(19,0);
	A9=string(19,9);
	
	dfs(0,18);
	cout<<ret<<endl;
}

まとめ

これよく一発で通ったな。