SRM 437 Div1 Medium TheInteger

問題概要

整数nが与えられる。
n以上で、数字がちょうどk種類であるような、最小の整数を求めよ。

制約条件

n≦10^18
1≦k≦10

方針

場合分けで解こうとしたら解けなかった。

dp[i][mask][j]を、
数字をi番目まで見て、maskで表せる数字を使い、
j=1ならi番目まででnより大きくなっている状態の、最小の数とする。

すると、下のように表を更新するdpができる。

ソースコード

typedef unsigned long long ll;
ll dp[20][1<<10][2];

class TheInteger {
	public:
	long long find(long long n, int k) 
	{
		int d[20],m=0;
		for(ll i=n;i;i/=10)d[m++]=i%10;
		reverse(d,d+m);
		
		if(m<k){
		//nの桁数がkより小さかったら102345のような答えを直接作る。
			int a[10],ans=0; rep(i,k)a[i]=i;
			swap(a[0],a[1]);
			rep(i,k)ans*=10,ans+=a[i];
			return ans;
		}
		
		rep(i,20)rep(j,1<<10)rep(k,2)dp[i][j][k]=~0ll;
		rep(i,10)if(i>=d[0])dp[0][1<<i][i>d[0]]=i;
		
		rep(i,m-1)rep(mask,1<<10)rep(j,2)if(dp[i][mask][j]!=~0ll)rep(k,10){
			
			if(k<d[i+1]&&j==0)continue;
			ll &next=dp[i+1][mask|1<<k][j||k>d[i+1]];
			next=min(next,dp[i][mask][j]*10+k);
		}
		
		ll ans=~0ll;
		rep(i,1<<10)rep(l,2){
			int b=0;
			for(int j=i;j;j&=j-1)b++;
			if(b!=k)continue;
			ans=min(ans,dp[m-1][i][l]);
		}
		if(ans==~0){
		//答えがnと同じ桁数に存在しなかった場合、(nの桁)+1桁の最小の数が答え。
		//1000...000234みたいなものを作る。
			int a; ans=0;
			rep(i,m+1){
				if(i==0)a=1;
				else if(1<=i&&i<m-k+3)a=0;
				else a=i+k-m-1;
				
				ans*=10; ans+=a;
			}
			return (long long)ans;
		}
		return (long long)ans;
	}
};