Google Code Jam 2016 Round1B : B. Close Match

最近桁DP系の毛嫌いっぷりが増加している。
https://code.google.com/codejam/contest/11254486/dashboard#s=p1&a=2

問題

一部の桁が不明な同じ桁数の2整数C,Jが与えられる。
不明な桁を最適に埋め、両者の差の絶対値を最小化せよ。

解法

桁DPの要領で解く。
上の桁から両者を比較し、CとJの値が異なる桁があったとする。
例えばある桁でC＞Jであれば、以降の桁はCを最小化、Jを最大化するように割り当てればよい。

まだ大小の差がついていない段階で値が不明な桁を見つけた場合、以下のような割り当てを総当たりすればよい。

• もう片方と同じ値
• もう片方とより1大きい値
• もう片方とより1小さい値

int L;
string C,J;
string AC,AJ;
ll CC,JJ;

void comp(string A,string B) {
	ll ta=atoll(A.c_str());
	ll tb=atoll(B.c_str());
	if(abs(CC-JJ)>abs(ta-tb) || (abs(CC-JJ)==abs(ta-tb) && ta<CC) || 
		(abs(CC-JJ)==abs(ta-tb) && ta==CC && tb<JJ)) {
		AC=A;
		AJ=B;
		CC=ta;
		JJ=tb;
	}
}
void small(string A,string B) {
	FORR(r,A) if(r=='?') r='9';
	FORR(r,B) if(r=='?') r='0';
	comp(A,B);
}
void large(string A,string B) {
	FORR(r,A) if(r=='?') r='0';
	FORR(r,B) if(r=='?') r='9';
	comp(A,B);
}


void dfs(int d,string A,string B) {
	if(d==L) {
		comp(A,B);
		return;
	}
	
	int i;
	// same
	if(A[d]==B[d] || A[d]=='?' || B[d]=='?') {
		string A2=A, B2=B;
		if(A2[d]=='?' && B2[d]=='?') A2[d]=B2[d]='0';
		else if(A2[d]=='?') A2[d]=B2[d];
		else if(B2[d]=='?') B2[d]=A2[d];
		dfs(d+1,A2,B2);
	}
	// A<B
	if(A[d]!='?' && B[d]!='?' && A[d]<B[d])  { string A2=A, B2=B; small(A2,B2);}
	if(A[d]=='?' && (B[d]!='?' && B[d]>'0')) { string A2=A, B2=B; A2[d]=B2[d]-1; small(A2,B2);}
	if((A[d]!='?' && A[d]<'9') && B[d]=='?') { string A2=A, B2=B; B2[d]=A2[d]+1; small(A2,B2);}
	if(A[d]=='?' && B[d]=='?')               { string A2=A, B2=B; A2[d]='0'; B2[d]='1'; small(A2,B2);}
	// A>B
	if(A[d]!='?' && B[d]!='?' && A[d]>B[d])  { string A2=A, B2=B; large(A2,B2);}
	if(A[d]=='?' && (B[d]!='?' && B[d]<'9')) { string A2=A, B2=B; A2[d]=B2[d]+1; large(A2,B2);}
	if((A[d]!='?' && A[d]>'0') && B[d]=='?') { string A2=A, B2=B; B2[d]=A2[d]-1; large(A2,B2);}
	if(A[d]=='?' && B[d]=='?')               { string A2=A, B2=B; A2[d]='1'; B2[d]='0'; large(A2,B2);}
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>C>>J;
	L=C.size();
	CC=0,JJ=1LL<<60;
	dfs(0,C,J);
	
	_P("Case #%d: %s %s\n",_loop,AC.c_str(),AJ.c_str());
}

まとめ

真ん中のif文もっときれいに書けるかもしれないけどゴリ押しした。