Codeforces #728 Div1 : B. Tree Array

3完で割といい順位になった回。
https://codeforces.com/contest/1540/problem/B

問題

木を成すグラフが与えられる。
ここから、以下の手順で数列を作る。

• まず、1つの点を等確率でランダムに選びマークを付ける。
• 以降、いずれかのマークをついた点に隣接する、マークしてない点を等確率でランダムに選び、マークを付ける。

上記作業の過程で、マークを付けた頂点の番号を順に並べた数列を作るとき、転送数の期待値を求めよ。

解法

頂点対(U,V) (U＜V)を総当たりし、Uより先にVがマークされる確率を求めよう。
最初の頂点Pが、P-Vのパス上にUがあったり、P-Uのパス上にVがある場合、以後の手順を問わず確率は0か1で決まる。
そうでない場合、Pから最寄りのU-V上の点Qを求めると、U-Q間の距離とQ-V間の距離から、U,Vどちらが先にマークされるかの確率をメモ化再帰で計算できる。

int N;
const ll mo=1000000007;
int C[202][202];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll memo[202][202];
ll win(int a,int b) {
	if(a==0) return 1;
	if(b==0) return 0;
	if(memo[a][b]>=0) return memo[a][b];
	
	return memo[a][b]=(win(a-1,b)+win(a,b-1))*modpow(2)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	cin>>N;
	FOR(x,N) FOR(y,N) C[x][y]=(x==y)?0:2020;
	FOR(i,N-1) {
		cin>>x>>y;
		C[x-1][y-1]=C[y-1][x-1]=1;
	}
	FOR(k,N) FOR(x,N) FOR(y,N) C[x][y]=min(C[x][y],C[x][k]+C[k][y]);
	ll ret=0;
	
	FOR(y,N) FOR(x,y) {
		int c=C[x][y];
		FOR(i,N) {
			int a=C[i][y];
			int b=C[i][x];
			int d=((a+b)-c)/2;
			
			a-=d;
			b-=d;
			ret+=win(a,b);
		}
	}
	ret=ret%mo*modpow(N)%mo;
	
	cout<<ret<<endl;
	
}

まとめ

1250ptだけど本番割とすんなり解いてるな。