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をいろいろ考えてたんですが…。