GCJ 2016 Round 1B B - Close Match
問題
Dashboard - Round 1B 2016 - Google Code Jam
問題概要
2チームが対戦していて，表示板にそれぞれのチームのスコアが表示されている(それぞれのスコアについて，先頭に複数の0がある可能性もある)．いま，表示板のいくつかの表示部分が壊れてしまってそこの数字が見えない．
2つのチームの表示板の状態がそれぞれと
で与えられる(壊れている部分が
?で表される)時，と
のスコアの差が最小になるように
?を埋めてスコアを答えよ．また，差が最小になるような組み合わせが複数あるときにはその中でが最小のものを，それでも複数ある場合には更にその中で
が最小のものを答えよ．
アイデア
まず，smallに関しては桁数が3以下なので，スコアの値としてあり得るのが001~999のどれかになる．よって，2チームのスコアを全探索(通り)することが可能．
しかし，largeは桁数が18以下なので，C++のlong long型に収まる範囲ではあるが全探索はムリ．やるべきこととしては?のところに数字を埋めていくということだが，まず全く同じ値にできる可能性が有るということを考えておきたい．それは?を埋めることによってか，もしくは最初から壊れているところなどなくて全ての桁が一致しているかというどちらかになる．
だからといって，?が来たらその桁を一致させるようにして，どちらも?だったら小さいほうが良いから0を選んどけばいい，ということにはならない．例えば，??0と?99という組が与えられたら，最適なのは090と099ではなく，100と099ということになる．つまり，上位の桁から見ていって有る桁までは同じ値を持ち，その下から違う値になるというものが最適になりうつこともあるわけである．
左から順に文字列を見ていって，初めて違う値の桁にたどりついたらどういうことが起こるかというと，その時点でどちらが大きいスコアになるかが決定されるということである．そして，大小が決まってしまえばそこから先の?をどのように埋めていけば最適なのかというのは貪欲に?に入る値を決めていけるのだ．なぜなら，大きいと確定してしまった方はそれ以上大きくする必要性がないのでできるだけ小さい方向，つまり?には全て0を入れるのが最善であり，小さいと決まった方にはそれ以降の?を9で埋めるのが最善である．
以上のことをまとめると，文字列を見ながら左から次のようにしていくのが最適な解を見つける手法と言える：
(1)両方数字が決まっていて同じ時
次の桁に進む．
(2)両方数字が決まっていて違う時
その時点で大小が決定するので，それ以降の?を前述のとおり大きい方は全て0で，小さい方は全て9で埋めて答え完成．
(3)片方だけが数字で，もう片方が?の時
数字が9じゃなければ，?に数字+1の値を入れてみる．これによって大小関係を決定する要因がここで生まれ，それ以降のものを(2)のように埋めてみて，差をみて答えを更新する．
数字が0じゃなければ，?に数字-1の値を入れてみる．それ以降を(2)のように埋めてみて，答えを更新する．
同じ数字を?に入れて，次の桁へ進む．
(ここで，DFSのような全探索はなぜ必要ではないのかというと，大小関係が生まれるような状況は既に試したし，それ以上の差を作るのは差を最小にする上で最適ではない．よって，大小を試し終わったら同じ数字だけを次のステップに持ち越せばよいのである．つまり，大小関係が決定する桁の位置をずらしながら全探索していくイメージ．)
(4)両方?の時
(0,1)と代入してみる．大小関係が決まるので，(以下略)．(1,0)も試してみる．
(0,0)を代入して次へ進む(これも，0と1以外は差の最小化とと
の最小化という条件から試す必要がないのである)．
このように試していくことで，時間計算量はで実現できる．
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second bool num(char c) { return ('0'<=c && c<='9'); } ll ab(ll x) { return (x>0?x:-x); } int main() { int T; cin >>T; rep(t,T) { string C,J; cin >>C >>J; ll dif=999999999999999999; string x="#",y="#"; int n=C.size(); rep(i,n) { if(num(C[i]) && num(J[i])) { if(C[i]<J[i]) { //Jが大きいことが確定 rep(j,n) if(C[j]=='?') C[j]='9'; rep(j,n) if(J[j]=='?') J[j]='0'; //更新 ll a=atoll(C.c_str()); ll b=atoll(J.c_str()); if(ab(a-b)<dif) { x=C; y=J; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=C; y=J; } else { if(C<x || (C==x&&J<y)) { x=C; y=J; } } } } else if(C[i]>J[i]) { //Cが大きいことが確定 rep(j,n) if(C[j]=='?') C[j]='0'; rep(j,n) if(J[j]=='?') J[j]='9'; //更新 ll a=atoll(C.c_str()); ll b=atoll(J.c_str()); if(ab(a-b)<dif) { x=C; y=J; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=C; y=J; } else { if(C<x || (C==x&&J<y)) { x=C; y=J; } } } } } else if(num(C[i])) { if(C[i]!='9') { string tc=C, tj=J; tj[i]=C[i]+1; //tjが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='9'; rep(j,n) if(tj[j]=='?') tj[j]='0'; //更新 ll a=atoll(tc.c_str()); ll b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } } if(C[i]!='0') { string tc=C, tj=J; tj[i]=C[i]-1; //tcが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='0'; rep(j,n) if(tj[j]=='?') tj[j]='9'; //更新 ll a=atoll(tc.c_str()); ll b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } } J[i]=C[i]; } else if(num(J[i])) { if(J[i]!='9') { string tc=C, tj=J; tc[i]=J[i]+1; //tcが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='0'; rep(j,n) if(tj[j]=='?') tj[j]='9'; //更新 ll a=atoll(tc.c_str()); ll b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } } if(J[i]!='0') { string tc=C, tj=J; tc[i]=J[i]-1; //tjが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='9'; rep(j,n) if(tj[j]=='?') tj[j]='0'; //更新 ll a=atoll(tc.c_str()); ll b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } } C[i]=J[i]; } else { string tc,tj; //(0,1)を試す tc=C; tj=J; tc[i]='0'; tj[i]='1'; //tjが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='9'; rep(j,n) if(tj[j]=='?') tj[j]='0'; //更新 ll a=atoll(tc.c_str()); ll b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } //(1,0)を試す tc=C; tj=J; tc[i]='1'; tj[i]='0'; //tcが大きいことが確定 rep(j,n) if(tc[j]=='?') tc[j]='0'; rep(j,n) if(tj[j]=='?') tj[j]='9'; //更新 a=atoll(tc.c_str()); b=atoll(tj.c_str()); if(ab(a-b)<dif) { x=tc; y=tj; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=tc; y=tj; } else { if(tc<x || (tc==x&&tj<y)) { x=tc; y=tj; } } } C[i]=J[i]='0'; } } //最後に更新 ll a=atoll(C.c_str()); ll b=atoll(J.c_str()); if(ab(a-b)<dif) { x=C; y=J; dif=ab(a-b); } else if(ab(a-b)==dif) { if(x=="#") { x=C; y=J; } else { if(C<x || (C==x&&J<y)) { x=C; y=J; } } } printf("Case #%d:", t+1); cout <<" "<<x<<" "<<y<<endl; } return 0; }
