Google Code Jam 2016 Round 1B

Round 1Bに参加した。
結果は、oooxoxで見事Round 1Cへの出場権を獲得した。
とりあえず復習したので、ソースをはっておく。

A. Getting the Digits
0-9の数字をアルファベットで書いたときに、Zは"ZERO"にしか出てこない。
よってZの数を数えれば、0の数がわかる。
0は消えたので、1-9のアルファベット表記を考える。Xは"SIX"にしか出てこない。
よってXの数を数えれば、6の数がわかる。
6は消えたので{1,2,3,4,5,7,8,9}のアルファベット表記を考える。Wは"TWO"にしか出てこない。よってWの数を数えれば、2の数がわかる。
....
という方針で解く。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int freq[128];
int cnt[10];
tuple<string, char, int> vs[] = {
  {"ZERO", 'Z', 0}, 
  {"SIX", 'X', 6},
  {"TWO", 'W', 2},
  {"FOUR", 'U', 4},
  {"THREE", 'R', 3},
  {"FIVE", 'F', 5},
  {"ONE", 'O', 1},
  {"SEVEN", 'S', 7},
  {"EIGHT", 'T', 8},
  {"NINE", 'I', 9}
};

void solve() {
  string s;
  cin >> s;
  memset(freq, 0, sizeof(freq));
  memset(cnt, 0, sizeof(cnt));

  for (auto &c: s)
    freq[c]++;

  for (auto &v : vs) {
    string x;
    char y;
    int z;
    tie(x,y,z) = v;

    cnt[z] = freq[y];
    for (auto &c: x)
      freq[c] -= cnt[z];
  }

  for (int i = 0; i < 10; i++)
    for (int j = 0; j < cnt[i]; j++)
      cout << i;
  cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

B. Close Match
2つの数をA, Bとする。Aの桁数をnとする。
A > Bが確定ならば、Aの後続の?は0で埋め、Bの?は9で埋めればよい。
A < Bが確定ならば、Aの後続の?は9で 埋め、Bの?は0で埋めればよい。

k桁目の値(k=0,1,...,nでループ)が決まると、はじめて上記のいずれかが確定するとする。
すると、i < kまではA[i]とB[i]は完全一致でなければならない。
k桁目の値は全列挙。
k+1桁目以降は、0、または、9で埋めればよい。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;
long long diff;
string A, B;
string ra, rb;

void update(const string &a, const string &b) {
  long long d = abs(stoll(a) - stoll(b));
  if (make_tuple(d, a, b) < make_tuple(diff, ra, rb)) {
    diff = d;
    ra = a;
    rb = b;
  }
}

void doit(int k, int p, int q, int r, int s) {
  string a = A;
  string b = B;
  int n = A.size();
  REP (i, k) {
    if (a[i] == '?' && b[i] == '?')
      a[i] = b[i] = '0';
    else if (a[i] == '?')
      a[i] = b[i];
    else if (b[i] == '?')
      b[i] = a[i];
  }
  if (k < n && a[k] == '?') a[k] = '0' + p;
  if (k < n && b[k] == '?') b[k] = '0' + q;
  FOR (i, k, n) {
    if (a[i] == '?') a[i] = r ? '9' : '0';
    if (b[i] == '?') b[i] = s ? '9' : '0';
  }
  update(a, b);
}

void solve() {
  cin >> A >> B;
  diff = oo;
  int n = B.length();

  REP (k, n+1) REP (p, 10) REP (q, 10) REP (r, 2) REP (s, 2) {
    doit(k, p, q, r, s);
  }
  
  cout << ra << " " << rb << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

C. Technobabble
第一ワードと第二ワードをノードと考えてグラフを構築する。
第一ワードvと第二ワードwがtopicを構成するとき、枝(v, w)をはる。
すると、このグラフは二部グラフになることがわかる。

ある枝集合を選ぶと、すべてのノードが少なくとも1つの枝によってリンクされる
<=>
使わなかった枝はfakeとなる

と考えることができる。fakeの最大値が欲しいので、上記の条件を満たす最小の枝集合を選べばいい。これは最小辺カバーであり、

|最小辺カバー| = ノード数 - |最大マッチング|

という関係から、最大マッチングを求めれば計算できる。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

class BipartiteMatching {
  int V;
  vector<vector<int> >G;
  vector<int> match;
  vector<bool> used;
  
  bool dfs(int v) {
    used[v] = true;
    for (int i = 0; i < (int)G[v].size(); i++) {
      int u = G[v][i];
      int w = match[u];
      if (w < 0 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  
 public:
  BipartiteMatching(int v_size) : V(v_size), G(V), match(V), used(V) {}
  
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  int count() {
    int ret = 0;
    fill(match.begin(), match.end(), -1);
    for (int v = 0; v < V; v++) {
      if (match[v] < 0) {
        fill(used.begin(), used.end(), false);
        if (dfs(v))
          ++ret;
      }
    }
    return ret;
  }
};


int n;
string a[1000], b[1000];

map<string, int> s2id(string s[], int n) {
  map<string, int> ret;
  REP (i, n) {
    if (!ret.count(s[i])) {
      int l = ret.size();
      ret[s[i]] = l;
    }
  }
  return ret;
}

void solve() {
  cin >> n;
  REP (i, n) cin >> a[i] >> b[i];
  auto aid = s2id(a, n);
  auto bid = s2id(b, n);

  int an = aid.size();
  int bn = bid.size();

  BipartiteMatching bm(an + bn);
  REP (i, n) bm.add_edge(aid[a[i]], an + bid[b[i]]);
  int edge_cover = an + bn - bm.count();
  cout << n - edge_cover << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}