AtCoder ARC #009 : D - 覚醒ノ高橋君

本番では時間切れした問題。
Writerが実装ゲーだと言っていたけど、確かに実装ゲーだ。
http://arc009.contest.atcoder.jp/tasks/arc009_4

最初の文面に市同士の連結についていろいろ書いてあるが、A個の市がA-1個の町を共有しているので、市同士では木を構成しており、閉路はない。

よって、手順としては下記の通り。

• 各市内で、全域木とそのコストを列挙する
• 各市ごとにDPし、合計コストの個数をカウントする

N個の点から全域木を作るには、N-1個の辺を選ぶわけだが、おおむね２種類の方法がある。

• DFSで閉路ができないようN-1個の辺を選ぶ
• bitdpでN-1個の辺を選び、全域木になることを確認する

今回は後者を選んだ。N=7なので、辺は最高21個であり、2^21個分チェックすればよい。

なお、N=7だと6辺残して最大15辺整備することになる。
後のDPのことを考えると、残る辺のコストを計算して、最後の全コストから減らす方が良い。
残る辺の全コストの累計は77市*6辺*77コスト、1市あたりのコストは最大77市*6辺なので、両者を掛けても何とかDPできる。

なお、各市内の全域木のコスト列挙は、コストごとの値をカウントする方がよく、コストのリストは作らない方が良い。
コストの値は6～77*6しかないが、全域木はCaylayの公式によるとN^(N-2)=16807個もある。

本問題は、実はサンプルに癖があって自分は完全にはまった。
というのも、各市はサンプルでは完全グラフだが、実際の問題ではそうとは限らないようだ。
おかげで３時間ぐらい考え込んでしまった。

全域木のコストができたらあとはDPしてカウントして行こう。
市１つあたり16807通りあるので、77市だと軽くオーバーフローする。
しかし求めるのはK<=7777777番目までなので、それ以上の値は適当に丸めておけばよい。

今回結構計算時間が危ない。最長で5秒近くかかっている。
全域木をDFSで求めると多少速くなるようだが。
そもそも問題で8秒とってあるのも珍しいね。

int A,T,K,M,TTC;
int N[100];
int C[100][10];
int MC[100];
int R[600][600];
int cost[100][500];
ll CO[40000];

int bitcount(int n) {
	int i=0;
	while(n>0) {i += n%2; n>>=1;}
	return i;
}

//全域木を求める
void enumcost(int city) {
	int NE,NC,i,rc,x,y,mask;
	int tx[7],ty[7],tn,tt;
	
	NC=N[city];
	MC[city]=0;
	
	FOR(x,NC) for(y=x+1;y<NC;y++) TTC += R[C[city][x]][C[city][y]];
	tt=0;
	NE=NC*(NC-1)/2;
	for(mask=1;mask<1<<NE;mask++) {
		int bc=bitcount(mask);
		int ng=0;
		if(bc!=NC-1) continue;
		tn=rc=0;
		x=0;y=0;
		int id;
		FOR(id,NE) {
			y++;
			if(y>=NC) {
				x++;
				y=x+1;
			}
			if(!(mask & (1<<id))) continue;
			tx[tn]=x;
			ty[tn]=y;
			tn++;
			rc += R[C[city][x]][C[city][y]];
			if(R[C[city][x]][C[city][y]]==0) ng++;
		}
		if(ng) continue;
		int ma=1;
		FOR(i,7) {
			FOR(id,tn) if(ma & ((1<<tx[id])|(1<<ty[id])))   ma |= (1<<tx[id]) | (1<<ty[id]);
		}
		if(ma==(1<<NC)-1){
			cost[city][rc]++;
			MC[city] = max(MC[city], rc);
			tt++;
		}
	}
}

void solve() {
	int x,y,i,j,rr,TM;
	ll p;
	
	GET3(&A,&T,&K);
	TTC=0;
	ZERO(N);
	ZERO(C);
	ZERO(cost);
	ZERO(R);
	
	FOR(i,A) {
		N[i]=GETi();
		FOR(j,N[i]) C[i][j]=GETi()-1;
	}
	
	M=GETi();
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		R[x][y]=R[y][x]=GETi();
	}
	
	FOR(i,A) enumcost(i);
	
	ZERO(CO);
	CO[0]=1;
	FOR(i,A) {
		for(j=77*77*6;j>=0;j--) {
			if(CO[j]==0) continue;
			FOR(x,MC[i]+1) if(cost[i][x]){
				CO[j+x] += CO[j]*cost[i][x];
				if(CO[j+x]>7777777) CO[j+x]=7777778;
			}
			CO[j]=0;
		}
	}
	
	for(j=77*77*6;j>=0;j--){
		if(CO[j]==0) continue;
		if(K<=CO[j]) {
			_P("%d\n",TTC-j);
			return;
		}
		K-=CO[j];
	}
	_P("%d\n",-1);
	return;
}

まとめ

DPがあるものの、あとは実装ゲー。
地道に実装すればなんとかなる。
ただ、サンプルで市を完全グラフにしておきながら、本番で非完全グラフにするのは勘弁願いたい…。
いや、勝手に思い込んだだけだけどさ。

全域木の問題は↓ここでも出ているね。
http://www.utpc.jp/2011/problems/spanning.html