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だけど本番割とすんなり解いてるな。