TopCoder SRM 599 Div1 Hard SimilarNames
evima先生作問。
問題
n人の人がいて、それぞれの名前が与えられる。
i番目の人の名前はj番目の人のprefixであるというグラフを作る。
このグラフの頂点に以下の制約を満たすように0〜n-1の番号を振りたい。
m個のinfoが与えられて、info1[i]番の頂点はinfo2[i]番の頂点のprefixになっている
条件を満たす頂点への番号の振り方の場合の数をmod 10^9 + 7で求めよ。
制約条件
n≦50
m≦8
同じ名前の人はいない。
方針
まずはprefix関係のグラフを作る。
ここにinfoのグラフを埋め込む場合の数を求め、あまった頂点をk個とすると、
残りは自由に番号を振れるので、k!倍すれば答えになる。
prefix関係は、自分のprefixの人に対して一番名前が長い人にだけ辺を張るようにすれば木になって、処理が簡単になる。
infoのグラフはDAGである。（ループがあった場合0通り）
木の根から順にDAGの頂点を割り当てていくが、
- DAGの子の頂点は親の頂点を先に埋め込まないと使えない
- 共通の子をもつ二頂点があったら、その二頂点は別の枝には埋め込みできない（どっちかがどっちかの祖先になってないとダメ）
という制約があるので、自分は木の頂点のうちどこまで埋め込みが終わったか、
DAGの頂点のうち次にどこから埋め込みを開始するかをキーとするDPを行った。
ひとつの頂点から複数の枝が出ているとき、
埋め込む頂点を割り振るのだが、それは部分集合のDPでやれば間に合う。
という感じで解法はすぐ浮かぶのだけど、実装が死だった。
mapで頂点をそのままメモったらTLEがきつすぎて、枝刈りいれてみたけどダメで、
vectorをやめてintにしてみたけどダメで、mapを止めて配列にして、とかゴリゴリ高速化してたらソースが意味不明になって死だった。
Editorialみたらめっちゃ綺麗なコードで書かれてて二度死。
状態を先に生成して番号を振っておけば簡単に書けたらしい。
計算量はO(n*5^m)らしいです。何故かはよくわかっていないや。
ソースコード
bool prefix(string a, string b){ return a.size() <= b.size() && a == b.substr(0, a.size()); } const int mod = (int)1e9 + 7; int sz; int dp[51][2][7000], id[1 << 16], id_cnt; vi ep[51], ei[51]; bool cantdivide[51][51], ci[51][51]; int parent[51], child[51]; char memo[7000][1 << 8]; inline void calc_ng(int v, int *pos){ int m = __builtin_popcount(v); memset(memo[id[v]], 0, 1 << 8); rep(i, 1 << m){ rep(j, m) if(i & 1 << j) rep(k, m) if(!(i & 1 << k) && cantdivide[pos[j]][pos[k]]) memo[id[v]][i] = 1; } } inline int calc(int r, int put, int v){ if(id[v] < 0) id[v] = id_cnt++; int &res = dp[r][put][id[v]]; int m = 0, lb = 0, pos[8]; if(res >= 0) return res; res = 0; rep(i, sz) if(v & 1 << i){ rep(j, ei[i].size()) if(parent[ei[i][j]] == i) lb++; pos[m++] = i; } if(v == 0) return res = 1; if(child[r] + put < m + lb) return res = 0; if(ep[r].empty()) return res = m == 1 && put && ei[pos[0]].empty(); if(put){ rep(i, sz) if(v & 1 << i){ bool bad = 0; rep(j, sz) if((v & 1 << j) && i != j && ci[j][i]) bad = 1; if(bad) continue; int nv = v ^ 1 << i; rep(j, ei[i].size()) if(parent[ei[i][j]] == i) nv |= 1 << ei[i][j]; (res += calc(r, 0, nv)) %= mod; } (res += calc(r, 0, v)) %= mod; return res; } int cur = 0, next = 1; int way[2][1 << 8] = {}, to[1 << 8] = {}; rep(i, 1 << m) rep(j, m) if(i & 1 << j) to[i] |= 1 << pos[j]; if(memo[id[v]][0] == -1) calc_ng(v, pos); way[0][(1 << m) - 1] = 1; rep(i, ep[r].size()){ memset(way[next], 0, sizeof(way[next])); rep(j, 1 << m) if(way[cur][j]) for(int k = j; ; k = (k - 1) & j){ if(!memo[id[v]][k]) (way[next][j ^ k] += way[cur][j] * (ll)calc(ep[r][i], 1, to[k]) % mod) %= mod; if(i == ep[r].size() - 1 || k == 0) break; } swap(cur, next); } return res = way[cur][0]; } class SimilarNames { public: int count(vector <string> names, vector <int> info1, vector <int> info2) { vi vinfo; rep(i, info1.size()) vinfo.pb(info1[i]), vinfo.pb(info2[i]); sort(all(vinfo)); vinfo.erase(unique(all(vinfo)), vinfo.end()); rep(i, info1.size()){ info1[i] = lower_bound(all(vinfo), info1[i]) - vinfo.begin(); info2[i] = lower_bound(all(vinfo), info2[i]) - vinfo.begin(); } sz = vinfo.size(); memset(memo, -1, sizeof(memo)); memset(cantdivide, 0, sizeof(cantdivide)); memset(parent, -1, sizeof(parent)); memset(ci, 0, sizeof(ci)); memset(child, 0, sizeof(child)); memset(dp, -1, sizeof(dp)); memset(id, -1, sizeof(id)); id_cnt = 0; int n = names.size(); bool gp[51][51] = {}, gi[51][51] = {}; bool cp[51][51] = {}; //, ci[51][51] = {} //closure vi rp, ri; //make graph rep(i, n) rep(j, n) gp[i][j] = cp[i][j] = i != j && prefix(names[i], names[j]); rep(i, n) rep(j, n) if(gp[i][j]) rep(k, n) if(cp[i][k] && cp[k][j]) gp[i][j] = 0; rep(i, info1.size()) gi[info1[i]][info2[i]] = 1; rep(i, n) rep(j, n) ci[i][j] = gi[i][j]; rep(k, n) rep(i, n) rep(j, n) ci[i][j] |= ci[i][k] && ci[k][j]; rep(i, n) rep(j, n) if(gi[i][j]) rep(k, n) if(ci[i][k] && ci[k][j]) gi[i][j] = 0; rep(i, n){ ep[i].clear(); ei[i].clear(); rep(j, n){ if(gp[i][j]) ep[i].pb(j); if(gi[i][j]) ei[i].pb(j); } } rep(i, n){ bool ok1 = 1, ok2 = 1; rep(j, n){ if(cp[j][i]) ok1 = 0; if(ci[j][i]) ok2 = 0; } if(ok1 && ep[i].size()) rp.pb(i); if(ok2 && ei[i].size()) ri.pb(i); } rep(i, n) rep(j, n) if(i != j) rep(k, n) if(ci[i][k] && ci[j][k]) cantdivide[i][j] = 1; rep(i, n) rep(j, n) if(i != j && (ci[i][j] || ci[j][i])) cantdivide[i][j] = 1; rep(i, n) rep(j, n) if(gi[j][i]){ parent[i] = j; break; } rep(i, n) rep(j, n) if(cp[i][j]) child[i]++; child[n] = inf; //check whether DAG or not rep(i, n) if(ci[i][i]) return 0; rep(i, rp.size()) ep[n].pb(rp[i]); int rii = 0; rep(i, ri.size()) rii |= 1 << ri[i]; ll res = calc(n, 0, rii); int cnt = n; rep(i, n){ bool ok = 0; rep(j, n) if(gi[i][j] || gi[j][i]) ok = 1; if(ok) cnt--; } for(; cnt; cnt--) res = res * cnt % mod; return res; } };
