TopCoder SRM 546 Div1 Medium FavouriteDigits

Div2 Hardかと思って解いたらDiv1 Mediumと同じ問題だった。
http://community.topcoder.com/stat?c=problem_statement&pm=12045

問題

最大15桁の整数N以上の数値で、各桁に数d1がc1個以上、d2がc2個以上含まれる最小の数値を返せ。

解法

まずN自身が題意を満たすか判定し、Nが条件を満たすならそれを返す。
Nが満たさないということは、Nより大きな数値で題意を満たす値を探さないといけない。

そこで、i桁目がNより大きい場合を考える。
下から(i+1)桁目より上はNと同じで、i桁目だけNより大きいとする。
i桁目を(Nのi桁目+1)～9で総当たりする。まず上からi桁目までにd1とd2が何個あるかカウントする。
d1とd2がそれぞれc1,c2に足りないなら、i桁目より下の位からd2やd1を敷き詰め、余ったら0を埋める。

この作業で得られる数値のうち、題意を満たす最小値を答えればよい。

class FavouriteDigits {
	public:
	ll p10[19];
	int d1,c1,d2,c2;
	
	int okok(ll v, int mv,int& tc1, int& tc2) {
		int ok=0,i,j=0;
		tc1=tc2=0;
		
		for(i=16;i>=mv;i--) {
			if(v/p10[i]) j++;
			if(j && ((v/p10[i])%10)==d1) tc1++;
			if(j && ((v/p10[i])%10)==d2) tc2++;
		}
		return (tc1>=c1) && (tc2>=c2);
	}
	
	long long findNext(long long N, int digit1, int count1, int digit2, int count2) {
		int i,j,tc1,tc2,x;
		d1=digit1; d2=digit2;
		c1=count1; c2=count2;
		if(d1>d2) swap(d1,d2), swap(c1,c2);
		
		ll ret=1LL<<60;
		p10[0]=1;
		FOR(i,18) p10[i+1]=10*p10[i];
		
		if(okok(N,0,tc1,tc2)) return N;
		
		for(i=17;i>=0;i--) {
			ll val = N/p10[i+1]*p10[i+1];
			FOR(j,10) {
				ll val2=val + j*p10[i];
				if(val2<=N) continue;
				okok(val2,i,tc1,tc2);
				
				FOR(x,i) {
					if(tc2<c2) tc2++, val2 += d2*p10[x];
					else if(tc1<c1) tc1++, val2 += d1*p10[x];
				}
				if(tc1>=c1 && tc2>=c2) ret = min(ret,val2);
			}
		}
		return ret;
		
	}
};

まとめ

大小判定の問題は、ケタ単位の処理なら10進数、bit演算なら2進数で桁毎に処理するってのは定番ネタとして覚えておくとよさそう。
O(N)の計算量をO(log N)に押さえられる。