TopCoder SRM 692 Div1 Easy HardProof

不参加回。朝だったので参加者も少な目。
https://community.topcoder.com/stat?c=problem_statement&pm=14334

問題

元の問題文をだいぶ意訳。
N頂点間の全頂点対に有向辺が張られている。
(i→j)を結ぶ辺にはそれぞれコストA[i][j]が張られている。

これらの辺のうち、一部の辺を用い、N頂点が連結になるようにしたい。
用いる辺のコストの最大値と最小値の差の最小値を求めよ。

解法

最大値と最小値はA[i][j]中登場する値以外が意味ないことはわかる。
あとは最小値を総当たりし、(最大値を増やすほど使える辺が増えるので)対応する最大値を二分探索すればよい。

最小値がO(N^2)通り、最大値の二分探索がO(logN)回なので、連結判定にO(N^2*logN)かかる。
そのため連結判定はWarshall-Floyd等時間のかかるものを利用するとTLEする。
以下のコードは、Nが小さいことを用い0から全頂点に移動できるか、全頂点から0に移動できるかをそれぞれO(N)で調べている。

地味にN==1がコーナーケースなので注意。

class HardProof {
	public:
	int N;
	vector <int> D;
	ll mask[51];
	
	ll cango(int from) {
		ll cur=1LL<<from;
		ll nex=1LL<<from;
		while(nex) {
			ll nn=0;
			int i;
			FOR(i,N) if(nex&(1LL<<i)) nn |= mask[i];
			ll alread =cur&nn;
			cur |= nn;
			nex = nn ^ alread;
		}
		return cur;
	}
	
	int ask(int mi,int ma) {
		int x,y,z;
		
		FOR(x,N) mask[x]=1LL<<x;
		FOR(y,N) FOR(x,N) if(D[y*N+x]>=mi && D[y*N+x]<=ma) mask[y] |= 1LL<<x;
		if(cango(0)!=(1LL<<N)-1) return 0;
		FOR(x,N) mask[x]=1LL<<x;
		FOR(y,N) FOR(x,N) if(D[y*N+x]>=mi && D[y*N+x]<=ma) mask[x] |= 1LL<<y;
		if(cango(0)!=(1LL<<N)-1) return 0;
		return 1;
	}
	
	int minimumCost(vector <int> d) {
		int ret=10101010;
		int ma,mi;
		vector<int> cand;
		int i;
		
		D=d;
		N=0;
		while(N*N<D.size()) N++;
		
		if(N==1) return 0;
		FOR(i,N*N) cand.push_back(D[i]);
		sort(cand.begin(),cand.end());
		cand.erase(unique(cand.begin(),cand.end()),cand.end());
		FOR(mi,cand.size()) {
			
			ma=cand.size();
			for(i=12;i>=0;i--) if(ma-(1<<i)>=mi && ask(cand[mi],cand[ma-(1<<i)])) ma-=1<<i;
			if(ma<cand.size() && cand[ma]-cand[mi]<ret) ret = cand[ma]-cand[mi];
		}
		return ret;
	}
}

まとめ

手元で解いたら2WAしたので出なくてよかったな…。