kmjp's blog

競技プログラミング参加記です

TopCoder SRM 696 Div1 Medium Clicounting

うーむ、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);
		
		
	}
}

まとめ

最大クリークライブラリあったら楽勝だったのか…。