Google Code Jam Qualification Round 2017

　Code Jam 2017の予選があった。ABCの3問を解いて、通過ラインを超えることができた。Dの問題を復習しておく。

問題
Fashion Show

考察

• 各モデル達はチェスのルーク、ビショップ、クイーンのどれかに対応する
• 8クイーン問題的に考えることができる
• ビショップとルークの問題を独立して考えることができる
• クイーンのポイントは2点なので、ビショップとルークの問題を解いてそのままマージすればOK
• 各配置問題は（行, 列）または（左斜め軸、右斜め軸）の二部グラフのマッチングをすればOK

ソースコード

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 n;
int m;
int bd[100][100];
int be[100][100];

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 getPair(int v) {
    return match[v];
  }
};

void solve() {
  cin >> n >> m;
  memset(bd, 0, sizeof(bd));
  REP (i, m) {
    char t;
    int y, x;
    cin >> t >> y >> x;
    --x, --y;
    if (t == 'x') bd[y][x] = 1;
    else if (t == '+') bd[y][x] = 2;
    else if (t == 'o') bd[y][x] = 3;
  }

  REP (i, n) REP (j, n) be[i][j] = bd[i][j];

  // rook
  BipartiteMatching rook(2 * n);
  set<int> used;
  REP (i, n) REP (j, n) if (bd[i][j] & 1) {
    used.insert(i);
    used.insert(j + n);
  }
  REP (i, n) REP (j, n) if (!used.count(i) && !used.count(j+n)) rook.add_edge(i, j+n);
  rook.count();
  REP (i, n) {
    int j  = rook.getPair(i);
    if (j != -1) {
      be[i][j-n] |= 1;
    }
  }
  
  // bishop
  BipartiteMatching bishop(4*n);
  used.clear();
  REP (i, n) REP (j, n) if (bd[i][j] & 2) {
    used.insert(n-1+i-j);
    used.insert(2*n-1+i+j);
  }
  REP (i, n) REP (j, n) {
    if (!used.count(n-1+i-j) && !used.count(2*n-1+i+j))
      bishop.add_edge(n-1+i-j, 2*n-1+i+j); 
  }
  bishop.count();
  REP (i, n) REP (j, n) {
    int d1 = n-1+i-j;
    int d2 = 2*n-1+i+j;
    if (bishop.getPair(d1) == d2)
      be[i][j] |= 2;
  }

  // output score
  int score = 0;
  REP (i, n) REP (j, n) {
    if (be[i][j] & 1) ++score;
    if (be[i][j] & 2) ++score;
  }
  cout << score << " ";

  // output changed arrangement
  int cnt = 0;
  REP (i, n) REP (j, n) cnt += bd[i][j] != be[i][j];
  cout << cnt << endl;

  REP (i, n) REP (j, n) {
    if (be[i][j] != bd[i][j]) {
      char t = be[i][j] == 3 ? 'o' : (be[i][j] == 1 ? 'x' : '+');
      cout << t << " " << i+1 << " " << j+1 << 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;
}