Google Code Jam 2021 Round 3 : A. Build-A-Pair

やはりRound3は難しい。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000436142/0000000000813aa8

問題

数字がN個与えられる。
これらの数字を2つの組に分け、並べ替えて正整数A,Bを作ったとする。
abs(A-B)の最小値を求めよ。

解法

• Nが奇数の場合
  • 片方が(N+1)/2桁、もう片方が(N-1)/2桁で桁数は確定する。
  • そこで、前者はN個の数字のうち小さい順に選び、後者は残った数字を大きい順に選べばよい。
  • ただし、leading zeroを避けるため、前者は先頭の数字だけは非0のものを選ぼう。
• Nが偶数の場合
  • 各数字の登場回数が偶数なら、A=Bを構築できるのは自明。
  • そうでない場合、A＞Bである場合、上から見てある桁でAはx、Bはy (x＞y)となる箇所があることになる。
  • そこで、x,yを総当たりしよう。x,yの配置される桁は下である方が差が小さくなるので、残った数字は2個ずつペアにしてx,yより上の桁に置くことを考える。そうすると、各数字の余りは0個か1個である。そこで残った数字を、「Nが奇数の場合」同様に小さい順半分をxの後に配置し、大きい順半分をyの後に配置しよう。
  • 注意点として、leading zeroを防ぐため、0のペアをx,yより上に置くには、0でないペアが1個以上存在しなければならない。
  • 0,9に関しては、無理にペアにして上の桁に置くより、下に残した方が良いケースがある。たとえば0x25と0y98よりは、x002と0y985の方が差が小さい。そこで0,9については、x,yの手前に持ってくるペアの数を総当たりしてしまおう。

int N;
string D;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>D;
	N=D.size();
	sort(ALL(D));
	ll ret=1LL<<60;
	
	if(N%2) {
		if(D[0]=='0') {
			FOR(i,N) {
				if(D[i]!='0') {
					swap(D[0],D[i]);
					break;
				}
			}
		}
		reverse(D.begin()+(N+1)/2,D.end());
		ll a=0,b=0;
		FOR(i,N) {
			if(i<=N/2) {
				a=a*10+D[i]-'0';
			}
			else {
				b=b*10+D[i]-'0';
			}
		}
		ret=abs(a-b);
	}
	else {
		int C[10]={};
		FORR(d,D) C[d-'0']++;
		
		FOR(i,10) if(C[i]%2) break;
		if(i==10) ret=0;
		
		FOR(y,10) if(C[y]) {
			C[y]--;
			FOR(x,y) if(C[x]) {
				C[x]--;
				int E[10]={};
				int ok=0;
				for(i=1;i<=8;i++) {
					E[i]=C[i]%2;
					if(C[i]>=2) ok=1;
				}
				
				for(E[0]=C[0]%2;E[0]<=C[0];E[0]+=2) {
					for(E[9]=C[9]%2;E[9]<=C[9];E[9]+=2) {
						if(ok==0&&E[9]==C[9]&&C[0]!=E[0]) continue;
						if(ok==0&&E[9]==C[9]&&x==0) continue;
						vector<int> V;
						FOR(i,10) FOR(j,E[i]) V.push_back(i);
						i=V.size();
						reverse(V.begin()+i/2,V.end());
						ll a=y,b=x;
						FOR(i,V.size()) {
							if(i<V.size()/2) {
								a=a*10+V[i];
							}
							else {
								b=b*10+V[i];
							}
						}
						ret=min(ret,abs(a-b));
					}
				}
				C[x]++;
			}
			C[y]++;
		}
		
	}
	
	
	_P("Case #%d: %lld\n",_loop,ret);
}

まとめ

シンプルな問題ながら、コーナーケースが多く面倒くさい。Round3のAっぽい問題。