Codeforces #1077 : Div1 C. Jerry and Tom

これは手間取ったけどまぁ解けて良かった。
https://codeforces.com/contest/2187/problem/C

問題

以下のDAGを成すN点のグラフを考える。

• N以外の各点uに対し、u→u+1の辺がある
• 追加でu→vの辺がいくつか与えられる。この時、u＜vであることが確定しているうえ、２つの辺が交差することはない。

f(i,j)を以下の値に定める。

• 先手は点i、後手は点jに駒を置き、以下のゲームを行う。
• 両者自身のターンで、駒を辺にそって隣接点に動かす。先手は必ず動かす必要があり、後手は止まっていてもよい。
• 操作後、両者の駒が同じ位置にいるなら後手の勝ち。異なる位置にいて、かつ先手が点Nに到達したら先手の勝ち。
• 先手が勝ちの場合、f(i,j)=0。先手が負け確定の場合、先手が負けるまでのターン数を最大化し、後手が最小化しようとしたときの後手の移動回数がf(i,j)

全部の(i,j)の組におけるf(i,j)を求めよ。

解法

基本的には両者は最速で点Nにいこうとする。
すると各点の行き先は一意に定まり、辺を逆向きにして考えるとこのグラフは有向の根付き木になる。

後手はターン数を最小化しようとするので、点vで両者が合流するのは、先手と後手がvの異なる子頂点のsubtreeにいて、かつ後手が先手より速くvに到達できるパターンである。
よって点vごとに、そこで合流する先手・後手の配置を求めよう。
これには、各点おいて、Subtreeにおける深さごとの頂点数をDequeで管理し、マージテクの要領でDequeの各要素の加算をしていけばよい。

int T,N,M;

int nex[202020];
vector<int> E[202020];
int C[202020];
ll S[202020];
deque<int> D[202020];
ll ret;

void dfs(int cur,int pre) {
	D[cur].clear();
	S[cur]=0;
	C[cur]=0;
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(D[e].size()>D[cur].size()) {
			swap(C[cur],C[e]);
			swap(S[cur],S[e]);
			swap(D[cur],D[e]);
		}
		int i;
		int lef=C[cur];
		ll pre=0;
		FOR(i,D[e].size()) {
			ret+=1LL*(i+1)*D[e][i]*lef;
			ret+=1LL*(i+1)*D[cur][i]*D[e][i];
			ret+=pre*D[e][i];
			pre+=1LL*(i+1)*D[cur][i];
			lef-=D[cur][i];
			D[cur][i]+=D[e][i];
		}
		C[cur]+=C[e];
	}
	
	D[cur].push_front(1);
	S[cur]+=C[cur];
	C[cur]++;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			nex[i]=i+1;
			E[i].clear();
		}
		FOR(i,M) {
			cin>>x>>y;
			nex[x-1]=max(nex[x-1],y-1);
		}
		FOR(i,N-1) E[nex[i]].push_back(i);
		ret=0;
		dfs(N-1,N-1);
		
		cout<<ret<<endl;
	}
}

まとめ

結構苦戦してるな…。