GCJ 2016 Round 1B B: Close Match

問題

Dashboard - Round 1B 2016 - Google Code Jam

解法

幅優先

コード

#include <bits/stdc++.h>
using namespace std;

string solve(const string &S, const string &T) {
  int N = S.size();
  queue<tuple<int, int64_t, int64_t>> que;
  que.emplace(0, 0, 0);
  vector<tuple<int64_t, int64_t, int64_t>> ans;
  while (!que.empty()) {
    int64_t i, s, t;
    tie(i, s, t) = que.front();
    que.pop();
    if (i == N) {
      ans.emplace_back(abs(s - t), s, t);
      continue;
    }

    if (s > t) {
      s = S[i] == '?' ? (s * 10 + 0) : (s * 10 + (S[i] - '0'));
      t = T[i] == '?' ? (t * 10 + 9) : (t * 10 + (T[i] - '0'));
      que.emplace(i + 1, s, t);
    } else if (s < t) {
      s = S[i] == '?' ? (s * 10 + 9) : (s * 10 + (S[i] - '0'));
      t = T[i] == '?' ? (t * 10 + 0) : (t * 10 + (T[i] - '0'));
      que.emplace(i + 1, s, t);
    } else {
      if (S[i] == '?' && T[i] == '?') {
        for (int64_t ss = 0; ss < 2; ++ss) {
          for (int64_t tt = 0; tt < 2; ++tt) {
            que.emplace(i + 1, s * 10 + ss, t * 10 + tt);
          }
        }
      } else if (S[i] == '?') {
        t = t * 10 + (T[i] - '0');
        que.emplace(i + 1, s * 10 + (T[i] - '0'), t);
        if (T[i] != '9') que.emplace(i + 1, s * 10 + (T[i] - '0') + 1, t);
        if (T[i] != '0') que.emplace(i + 1, s * 10 + (T[i] - '0') - 1, t);
      } else if (T[i] == '?') {
        s = s * 10 + (S[i] - '0');
        que.emplace(i + 1, s, t * 10 + (S[i] - '0'));
        if (S[i] != '9') que.emplace(i + 1, s, t * 10 + (S[i] - '0') + 1);
        if (S[i] != '0') que.emplace(i + 1, s, t * 10 + (S[i] - '0') - 1);
      } else {
        s = s * 10 + (S[i] - '0');
        t = t * 10 + (T[i] - '0');
        que.emplace(i + 1, s, t);
      }
    }
  }
  sort(ans.begin(), ans.end());
  int64_t i,s, t;
  tie(i, s, t) = ans[0];
  string rS = to_string(s);
  while (rS.size() < S.size()) rS = "0" + rS;
  string rT = to_string(t);
  while (rT.size() < S.size()) rT = "0" + rT;

  return rS + " " + rT;
}

bool check(const string &S, const int i) {
  string tmpi = to_string(i);
  if (tmpi.size() > S.size()) return false;
  while (tmpi.size() < S.size()) tmpi = "0" + tmpi;
  for (int si = 0; si < S.size(); ++si) {
    if (S[si] != tmpi[si] && S[si] != '?') return false;
  }
  return true;
}

string naive_solve(const string &S, const string &T) {
  vector<tuple<int, int, int>> ans;
  for (int i = 0; i < 1000; ++i) {
    if (!check(S, i)) continue;
    for (int j = 0; j < 1000; ++j) {
      if (!check(T, j)) continue;
      ans.emplace_back(abs(i - j), i, j);
    }
  }
  sort(ans.begin(), ans.end());
  int x, s, t;
  tie(x, s, t) = ans[0];
  string rS = to_string(s);
  while (rS.size() < S.size()) rS = "0" + rS;
  string rT = to_string(t);
  while (rT.size() < S.size()) rT = "0" + rT;

  return rS + " " + rT;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    string S, T;
    cin >> S >> T;

    cout << "Case #" << testcase << ": ";
    if (S.size() <= 3) {
      if (naive_solve(S, T) != solve(S, T)) {
        cerr << S << " " << T << endl;
        cerr << naive_solve(S, T) << endl;
        cerr << solve(S, T) << endl;
        assert(false);
      }
    }

    cout << solve(S, T) << endl;
  }
}