TopCoder SRM 548 Div2 Hard KingdomAndPassword

問題

n桁の0を含まない数字からなるパスワードがある。
新しいパスワードを、このパスワードの桁を入れ替えて作る。

ただし、i番目に数字restrictedDigits[i]が来てはならない。
作れるパスワードが複数あるときは、|古いパスワード-新しいパスワード|が最小になるものを作るものとし、それも複数ある場合はその中で最小のものを作るものとする。

新しいパスワードを求めよ。
パスワードを作ることが出来ない場合-1を返せ。

制約条件

n≦16
restrictedDigits[]の要素はちょうどn個

方針

典型的な桁DP + 経路復元。
なのだが、|古いパスワード-新しいパスワード|を最小化するのが少し厄介。

自分は、i桁目までで、ビットの集合jを使い、
(古いパスワード-新しいパスワード)が正の場合の最小値と、
負の場合の最大値を覚えてDPした。

これは、先頭からDPしていって、符号が一度確定したら、後は符号は全部同じなので、
絶対値が最小のものだけを覚えればいいため。

ソースコード

int d[20], n, prev[17][1 << 16][2];
ll dp[17][1 << 16][2];

class KingdomAndPassword {
	public:
	long long newPassword(long long oldPassword, vector <int> restrictedDigits) 
	{
		n = 0;
		for(; oldPassword; oldPassword /= 10) d[n++] = oldPassword % 10;
		reverse(d, d + n);
		
		rep(i, n + 1) rep(j, 1 << n) rep(k, 2) dp[i][j][k] = inf;
		dp[0][0][0] = 0;
		
		rep(i, n) rep(j, 1 << n) rep(s, 2) if(dp[i][j][s] != inf) rep(k, n){
			if((j & 1 << k) || restrictedDigits[i] == d[k]) continue;
			
			ll nxt = dp[i][j][s] * 10 + d[i] - d[k];
			int ns = nxt < 0;
			if(abs(dp[i + 1][j | 1 << k][ns]) > abs(nxt)){
				dp[i + 1][j | 1 << k][ns] = nxt;
				prev[i + 1][j | 1 << k][ns] = k * 2 + s;
			}
		}
		
		if(dp[n][(1 << n) - 1][0] == inf && dp[n][(1 << n) - 1][1] == inf) return -1;
		vi ans;
		int i = n, j = (1 << n) - 1, s = abs(dp[n][(1 << n) - 1][0]) > abs(dp[n][(1 << n) - 1][1]);
		while(i > 0){
			ans.pb(d[prev[i][j][s] / 2]);
			int ns = prev[i][j][s] % 2;
			j &= ~(1 << prev[i--][j][s] / 2);
			s = ns;
		}
		ll res = 0;
		rep(i, n) res *= 10, res += ans[n - i - 1];
		return res;
	}
};