TopCoder SRM 548 Div2 Hard KingdomAndPassword

SRM548はSRM初参加の回。もちろん色なしなのでDiv2参加。
本番では解けなかった問題。なんとか自力で解答。
http://community.topcoder.com/stat?c=problem_statement&pm=11869

問題

0の桁を含まない数値Nが与えられる。
また、各桁に利用できない数値が与えられる。

この数値の各桁を並べ替え、できるだけ元の数値との差が小さい値を作れ。

解法

前処理としてbitDPを用い、元のN中にあるいくつかの桁をから生成できる最大値・最小値を求めておく。

次に上の位からDFSで求めていく。
DFSの引数として、利用可能な桁の数値をbitmapで渡す。
DFSでは、このbitmapをもとに今の桁に当てはめる数値を総当たりで求めていく。

• 今見ている桁が、元のNより当てはめる数値が大きいなら、残りの桁は最小化したいので前処理した最小値を埋める。
• 今見ている桁が、元のNより当てはめる数値が小さいなら、残りの桁は最大化したいので前処理した最大値を埋める。
• 今見ている桁が、元のNより当てはめる数値が一致するなら、次の桁に進む。

それぞれで得られる値のうち、元の数値にもっとも近いものを採用すればよい。

ll mins[1<<17],maxs[1<<17];
ll mint[1<<17],maxt[1<<17];

class KingdomAndPassword {
	int L;
	vector<int> rd;
	ll op,d10[20];
	vector<int> num;
	
	public:
	long long dfs(int mask, ll val) {
		int bt = __builtin_popcount(mask)-1;
		ll best = -1LL<<61;
		int vis[10];
		
		if(mask==0) return val;
		ZERO(vis);
		
		int i;
		FOR(i,L) {
			if((mask & (1<<i))==0) continue;
			if(num[i]==rd[L-1-bt]) continue;
			if(vis[num[i]]) continue;
			vis[num[i]]++;
			
			ll t;
			if(num[i]<num[bt]) t = val + d10[bt]*num[i] + maxs[mask ^ (1<<i)];
			else if(num[i]>num[bt]) t = val + d10[bt]*num[i] + mins[mask ^ (1<<i)];
			else t = dfs(mask ^ (1<<i), val + d10[bt]*num[i]);
			
			if(abs(t)>=1LL<<60) continue;
			//if(bt==L-2) _P("%x %x %lld %lld\n",mask,i,val,t);
			if((abs(best-op) > abs(t-op)) || ((abs(best-op) == abs(t-op))&&op<best))
				best = t;
		}
		if(best<0) return -1LL<<60;
		return best;
	}
	
	long long newPassword(long long oldPassword, vector <int> restrictedDigits) {
		int i,j,x,y,bt;
		L = restrictedDigits.size();
		
		op=oldPassword;
		rd=restrictedDigits;
		
		d10[0]=1;
		FOR(i,L) d10[i+1]=d10[i]*10;
		num.clear();
		FOR(i,L) num.push_back(oldPassword%10),oldPassword/=10;
		
		FOR(i,1<<L) mins[i]=1LL<<60,maxs[i]=-1LL<<60;
		for(y=1;y<=L;y++) {
			FOR(i,1<<L) mint[i]=1LL<<60,maxt[i]=-1LL<<60;
			mint[0]=maxt[0]=0;
			FOR(i,1<<L) {
				bt = y-1-__builtin_popcount(i);
				if(__builtin_popcount(i)==y) mins[i]=mint[i],maxs[i]=maxt[i];
				if(bt<0) continue;
				FOR(x,L) if((i&(1<<x))==0 && num[x]!=rd[L-1-bt]) {
					if(mint[i]!=1LL<<60) {
						mint[i|(1<<x)] = min(mint[i|(1<<x)], mint[i]+num[x]*d10[bt]);
						maxt[i|(1<<x)] = max(maxt[i|(1<<x)], mint[i]+num[x]*d10[bt]);
					}
					if(maxt[i]!=-1LL<<60) {
						mint[i|(1<<x)] = min(mint[i|(1<<x)], maxt[i]+num[x]*d10[bt]);
						maxt[i|(1<<x)] = max(maxt[i|(1<<x)], maxt[i]+num[x]*d10[bt]);
					}
				}
			}
		}
		ll ret = dfs((1<<L)-1,0);
		if(ret<0) return -1;
		return ret;
	}
};

まとめ

以前解けなかった問題が解けるようになったのは、成長が感じられていいね。