SRM 371

Topcoderの環境をUbuntuで作ったので試してみました。

昔のSRMだとあまり考察がなくて解きやすく、実装力をつけるのにもってこいですね。

Easy
一周するとwidth-2, height-2の場合に帰着できて、あとはwidth==2or1の場合分けをやる。

struct SpiralRoute {
  int width;
  int length;
  pi loop(int a, int b) {
	  if(a == 1) return pi(0, b - 1);
	  if(b == 1) return pi(a - 1, 0);
	  if(a == 2 || b == 2) return pi(0, 1);
	  pi res = loop(a - 2, b - 2);
	  res.fst++; res.sec++;
	  return res;
  }
  vector<int> thronePosition(int _width, int _length) {
    width = _width, length = _length;
	pi p = loop(width, length);
	vector<int> res;
	res.pb(p.fst); res.pb(p.sec);
    return res;
  }
};

Middle
最小費用流流すだけ。

struct ChessMatchup {
  vector<int> us;
  vector<int> them;
  int maximumScore(vector<int> _us, vector<int> _them) {
    us = _us, them = _them;
	int n = sz(us);
	MCF::init(2 * n + 2);
	int s = 2 * n, t = 2 * n + 1;
	rep(i, 0, n) {
		MCF::add_edge(s, i, 1, 0);
		MCF::add_edge(i + n, t, 1, 0);
	}
	rep(i, 0, n) {
		rep(j, 0, n) {
			if(us[i] > them[j]) MCF::add_edge(i, j + n, 1, -2);
			else if(us[i] == them[j]) MCF::add_edge(i, j + n, 1, -1);
			else MCF::add_edge(i, j + n, 1, 0);
		}
	}
    return -MCF::get(s, t, n);
  }
};

Hard
連結成分ごとにトポロジカルソートの数をbitdpで求めてあげればいいだけなのだが、かなりてこずった。

struct RaceOrdering {
  int n;
  vector<int> first;
  vector<int> second;
  vector<int> G[50];
  vector<int> C[50];
  int cnt[50];
  int pre[50];
  bool used[50];
  ll dp[(1 << 20)];

  void dfs(int v, int k) {
	  used[v] = true;
	  C[k].pb(v);
	  rep(i, 0, sz(G[v])) {
		  int n = G[v][i];
		  if(!used[n]) dfs(n, k);
	  }
  }

  int countOrders(int _n, vector<int> _first, vector<int> _second) {
    n = _n, first = _first, second = _second;
	C_init(n + 10);
	int m = sz(first);
	rep(i, 0, m) {
		G[second[i]].pb(first[i]);
		G[first[i]].pb(second[i]);
		cnt[second[i]]++;
	}
	rep(i, 0, n) debug(i, cnt[i]);
	int k = 0;
	rep(i, 0, n) {
		if(!used[i]) dfs(i, k++);
	}
	rep(i, 0, n) G[i].clear();
	rep(i, 0, m) {
		G[first[i]].pb(second[i]);
	}
	memset(used, 0, sizeof(used));
	rep(i, 0, k) {
		while(true) {
			bool found = false;
			rep(j, 0, sz(C[i])) {
				if(cnt[C[i][j]]) found = true;
			}
			if(!found) break;
			found = false;
			rep(j, 0, sz(C[i])) {
				int n = C[i][j];
				if(cnt[n] == 0 && !used[n]) {
					found = true;
					used[n] = true;
					int at = find(all(C[i]), n) - C[i].begin();
					rep(l, 0, sz(G[n])) {
						int nn = G[n][l];
						cnt[nn]--;
						pre[nn] |= (1 << at);
					}
				}
			}
			if(!found) return 0;
		}
	}
	ll ans = 1;
	rep(i, 0, n) debug(bitset<4>(pre[i]));
	rep(l, 0, k) {
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		int nn = sz(C[l]);
		rep(bit, 0, (1 << nn)) {
			debug(bitset<4>(bit), dp[bit]);
			rep(i, 0, nn) {
				if(bit & (1 << i)) continue;
				if((pre[C[l][i]] & bit) == pre[C[l][i]]) {
					ADD(dp[bit | (1 << i)], dp[bit]);
				}
			}
		}
		MUL(ans, dp[(1 << nn) - 1]);
	}
	rep(l, 0, k) {
		MUL(ans, fiv[sz(C[l])]);
	}
	MUL(ans, fac[n]);
    return ans;
  }
};

ブログの更新が空いちゃって良くなかったね。CodeFestival予選CのEFをいろいろ考えてたんですが…。