kmjp's blog

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

CSAcademy Round #19 : E. Road Trips

結構苦労した。
https://csacademy.com/contest/round-19/#task/road-trips

問題

根付き木が与えられる。
各辺の距離はC[i]である。
M人の子供が根からいずれかの葉に向け移動していく。
各子供jには値V[j]が設定されている。

複数の子供がある辺を通過した場合、(通過した子供のV[j]の最小値)×C[i]がスコアとして加算される。
子供の移動先の葉を最適に設定した場合、スコアの総和を求めよ。

解法

M人の子供がS個の葉頂点に移動するとする。
その場合、V[j]の上位(S-1)人がバラバラの葉頂点に移動し、残り(M-S+1)人がまとまって上位陣とは別の頂点に移動するとよい。
後者の移動経路については、結局(Vの最小値)×C[i]がスコアに加算される。

よって、到達する葉頂点数Sを決めると、考えるべき子供も上位(S-1)人+最下位1人だけ考えればよい。
以下Sを1~Mまで総当たりし、それぞれのスコアの最大値を求めよう。
その際、S人のうちV[j]の小さい順にどの頂点を割り振るか考えていこう。

以下の通りbitDPで解く。
dp(S,mask) := 到達葉頂点数がSであり、S人中V[j]の低いbitcount(mask)人の到達先がmaskであるときのスコアの総和の最大値

今i番目の葉頂点の到達者がいない状態で、新規にi番の頂点の到達者が現れた場合のスコアの更新を考える。
すなわち、dp(S,mask xor (2^i))の値からdp(S,mask)を求めることを考える。
これは、下からbitcount(mask)番目のV[j]の人の行先をi番の葉頂点とすることになる。
よって、途中までの経路はよりV[j]の低い人と一緒に移動する可能性がある。

これを具体的に考えよう。
(mask xor (2^i))のbitmaskに含まれる頂点kそれぞれに対しLCA(i,k)を求め、そのうち最も根から遠い頂点をrとする。
根からrまではよりV[j]の低い人と一緒に移動するので、スコアは増加しない。
r→i番の葉頂点までの距離とV[j]の積の分だけスコアが増加する。

上記処理は愚直に組むとO(M^3*2^M*logN)かかる。
葉頂点は最大M個しかないので、LCAは先にM^2通り求めておくことで、logNを前処理で完了されることができる。
また、iとmaskに対するrの値を前処理しておくとループが1個へる。
両者わせるとO(N+M^2*2^M)で済むようになる。

int N,M;
int V[101010];
vector<pair<int,int>> E[101010];

int P[21][101010];
ll D[101010];
ll dist[101010];

vector<int> L,C;

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void dfs(int cur,int pre,ll di,int d) {
	D[cur]=d;
	dist[cur]=di;
	P[0][cur]=pre;
	
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,di+e.second,d+1);
}

ll dp[1<<18];
int LCA[20][20];
ll lowest[18][1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>V[i];
	
	FOR(i,N-1) {
		cin>>x>>y>>r;
		x--,y--;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
	}
	dfs(0,0,0,0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	
	FOR(i,N) if(i && E[i].size()==1) L.push_back(i);
	
	FOR(y,L.size()) FOR(x,L.size()) LCA[x][y] = lca(L[x],L[y]);
	FOR(i,1<<L.size()) {
		FOR(x,L.size()) if(i & (1<<x)) {
			FOR(y,L.size()) if(x!=y && (i & (1<<y))) lowest[x][i]=max(lowest[x][i],dist[LCA[x][y]]);
		}
	}
	
	sort(V,V+M);
	
	
	ll ret=0;
	for(x=1;x<=L.size();x++) {
		ll V2[20]={};
		FOR(i,x) {
			if(i==0) V2[i]=V[i];
			else V2[i]=V[i+(M-x)];
		}
		
		for(int mask=1;mask<1<<L.size();mask++) {
			int id=__builtin_popcount(mask)-1;
			if(id>=x) continue;
			dp[mask]=-1LL<<60;
			FOR(i,L.size()) if(mask & (1<<i)) {
				dp[mask]=max(dp[mask], dp[mask ^ (1<<i)] + (dist[L[i]]-lowest[i][mask])*V2[id]);
			}
			ret = max(ret, dp[mask]);
		}
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

本番LCA使うところに頭が至らなかった…。