うーむ、yukicoder頑張っておくべきだったか。
https://community.topcoder.com/stat?c=problem_statement&pm=14340
問題
Div2 Hardと同じ。ただしNの上限は38、Mの上限は10である。
TopCoder SRM 696 Div2 Hard Clicountingd2 - kmjp's blog
解法
最大クリークを求める効率の良いライブラリを持っていると、2^M回そのライブラリを動かすだけで解ける。
別解法として、自分はCodeforces上の以下のコメントを参考に解いた。
http://codeforces.com/blog/entry/46478?#comment-309518
Div2 Hardの解法に、半分全列挙を組み合わせて解く。
N個の頂点を半々に分けよう。
その際、辺の有無が不明な辺をもつ点は片方に寄せる。
Mが10以下なことからそのような頂点は20以下であるため、以下の解法で頂点を40個に決め打ちし、20個ずつに分けた。
その際、不明な辺をもつ点を前半に固めた。
まず後半20個について、Div2 Hard同様の処理を行う。
ただ、Div2 Hardでは辺の有無のbitmaskに対して最大クリークを求めたが、今回は後半20個のうち頂点を幾つか選んだ場合、その中における最大クリークを求めよう。
すなわち dp(mask) := maskに指定される頂点群に含まれる最大クリークの頂点数 とする。
次に前半20個について、Div2 Hard同様に今度こそ辺の有無のbitmaskに対する最大クリークを求めよう。すなわち以下のようにする。
dp2(mask) := maskに指定される辺が有効な場合の最大クリーク
前半20個のうち、mask2に相当する頂点群がクリークを成すとし、その場合maskに相当する辺が存在しなければならないとする。
mask2に該当する前半の頂点が、後半20個の頂点それぞれのどれと辺が結ばれているかを求めると、mask2に相当する後半20個中の頂点群mask3が求められる。
最初の後半の処理よりdp(mask3)はわかっているので、
dp2(mask) = bitcount(mask2) + dp(mask3)
の要領でdp2(mask)を求められる。
最後にまたdp2に高速ゼータ変換を適用すると、dp2をすべて求められる。
上記解法はO(2^(N/2)*N^2)なので割とギリギリ。
int first[20][20]; int firsec[20]; int second[20][20]; int fi[1<<10]; int sc[1<<20]; map<pair<int,int>,int> M; class Clicounting { public: int count(vector <string> g) { int i,x,y,mask; ZERO(fi); ZERO(sc); ZERO(firsec); M.clear(); while(g.size()<40) { FORR(s,g) s+="0"; g.push_back(string(g[0].size(),'0')); } vector<int> V; int did[40]={}; FOR(i,40) if(std::count(g[i].begin(),g[i].end(),'?')) V.push_back(i), did[i]=1; FOR(i,40) if(did[i]==0) V.push_back(i); int numh=0; FOR(y,20) { first[y][y]=second[y][y]=1; FOR(x,y) { if(g[V[x]][V[y]]=='0') first[x][y]=first[y][x]=0; if(g[V[x]][V[y]]=='1') first[x][y]=first[y][x]=1; if(g[V[x]][V[y]]=='?') first[x][y]=first[y][x]=2, M[{x,y}]=M[{y,x}]=numh++; if(g[V[x+20]][V[y+20]]=='0') second[x][y]=second[y][x]=0; if(g[V[x+20]][V[y+20]]=='1') second[x][y]=second[y][x]=1; } FOR(x,20) firsec[x] |= (g[V[x]][V[y+20]]=='1')<<y; } FOR(mask,1<<20) { int yes=1; FOR(y,20) if(mask&(1<<y)) FOR(x,y) if(mask&(1<<x)) { if(second[x][y]==0) yes=0; } if(yes) sc[mask]=__builtin_popcount(mask); } FOR(mask,1<<10) fi[mask]=sc[(1<<20)-1]; FOR(i,20) FOR(mask,1<<20) sc[mask | (1<<i)] = max(sc[mask | (1<<i)], sc[mask]); FOR(mask,1<<20) { int need=0, yes=1,secmask=(1<<20)-1; FOR(y,20) if(mask&(1<<y)) { secmask &= firsec[y]; FOR(x,y) if(mask&(1<<x)) { if(first[x][y]==0) yes=0; if(first[x][y]==2) need |= 1<<M[{x,y}]; } } if(yes) fi[need] = max(fi[need],__builtin_popcount(mask) + sc[secmask]); } FOR(i,numh) FOR(mask,1<<numh) fi[mask | (1<<i)] = max(fi[mask | (1<<i)], fi[mask]); return accumulate(fi,fi+(1<<numh),0); } }
まとめ
最大クリークライブラリあったら楽勝だったのか…。