kmjp's blog

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

CODE FESTIVAL 2018 Final: H - Pothunter

これは勉強になりました。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_h

問題

N頂点の木を成す無向グラフが与えられる。
各辺には移動時間が設定されている。

このグラフにおいて、M回コンテストが行われる。
各コンテストでは、開始時間・終了時間・開催場所・優勝賞金の情報が与えられる。
コンテストの時間中ずっとその場所に滞在し、かつ他のコンテストに参加しない場合、コンテストに参加・優勝して賞金を得ることができる。
時刻0で任意の頂点から開始し、最適な移動経路を通ったとき、得られる優勝賞金の総和の最大値を答えよ。

解法

仮にグラフが平衡二分木であったとする。
以下の2値を管理し、時系列で更新していくことにしよう。
S(v) := その時点で頂点vに滞在している場合の賞金総和の最大値
T(c) := その時点でコンテストcに参加する場合の賞金総和の最大値

以下の更新タイミングを時系列にソートし、順次更新すればO(MlogN)で済む。

  • コンテストcが終了後、親方向に順次祖先の頂点vに対しS(v)を更新する
  • コンテストcが始まる前、親方向から順次祖先の頂点vに対しS(v)の値を元にT(c)を更新する

ただ、実際は木は平衡二分木とは限らないので、祖先の頂点数はO(N)になりうるので全体でO(MN)かかりうる。
そこで、グラフを繰り返し重心分解し、分割時の頂点を順次祖先とみなすようにしよう。
そうすると各頂点の祖先の頂点数はO(logN)となり間に合う。

int N,M;
int A[101010],B[101010],D[101010];
vector<pair<int,ll>> E[101010];
vector<pair<int,ll>> E2[101010];
int vis[101010];
int NV[101010];

ll st[101010],en[101010],C[101010],X[101010];

ll dp[70707];
ll tobe[70707];

int dfs(int cur,int pre) {
	NV[cur]=1;
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) NV[cur]+=dfs(e.first,cur);
	return NV[cur];
}

int dfs2(int cur,int pre,int TNV) {
	int tot=1;
	int ok=1;
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) {
		int c = dfs2(e.first,cur,TNV);
		if(c!=-1) return c;
		tot += NV[e.first];
		if(NV[e.first]*2>TNV) ok=0;
	}
	if((TNV-tot)*2>TNV) ok=0;
	if(ok) return cur;
	return -1;
}

int dfs3(int cur,int pre,int base,ll d) {
	E2[cur].push_back({base,d});
	FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) dfs3(e.first,cur,base,d+e.second);
}

void split(int cur) {
	int TNV = dfs(cur,-1);
	int center=dfs2(cur,-1,TNV);
	dfs3(center,-1,center,0);
	vis[center]=1;
	FORR(e,E[center]) if(vis[e.first]==0) split(e.first);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		x--;
		y--;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
	}
	
	split(0);
	
	vector<vector<ll>> ev;
	FOR(i,M) {
		cin>>st[i]>>en[i]>>C[i]>>X[i];
		C[i]--;
		
		FORR(e,E2[C[i]]) {
			ev.push_back({(int)st[i]-(int)e.second,1,e.first,i});
			ev.push_back({(int)en[i]+(int)e.second,0,e.first,i});
		}
	}
	sort(ALL(ev));
	ll ret=0;
	FORR(e,ev) {
		if(e[1]==1) {
			tobe[e[3]]=max(tobe[e[3]],dp[e[2]]+X[e[3]]);
		}
		else {
			dp[e[2]]=max(dp[e[2]],tobe[e[3]]);
			ret=max(ret,dp[e[2]]);
		}
	}
	
	cout<<ret<<endl;
}

まとめ

重心分解することで直径の長い木を直径に短い木に変換するテク、ほかにも使えそう。