kmjp's blog

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

AtCoder ABC #144 : F - Fork in the Road

こちらもABCのFにしてはあんまり迷わないかな…。
https://atcoder.jp/contests/abc144/tasks/abc144_f
 

問題

DAGを成すN頂点の有向グラフが与えられる。
(N番以外の)各頂点は、自身の番号より大きな番号に向け最低1本の有向辺をもつ。

頂点1→Nに有向辺に沿って移動することを考える。
その際、現在いる頂点を始点とする辺のうち、いずれかを等確率で選ぶ。

ここで、辺のうち1個を削除できるとする。ただし削除によりN番に移動できなくなるような削除方法は不可とする。
頂点1→Nに移動する遷移回数の期待値最小値を求めよ。

解法

dp(v) := v→N番に至る遷移回数の期待値
とする。すると
dp(N) = 0
dp(v) = 1+ avg(dp(e)) (eは頂点vから出ている有向辺の行き先)
となるので、後ろから値を埋めていくとO(M)で埋めきってdp(1)を求めることができる。

ここで、どの辺を削除するかを考える。
辺の始点を総当たりすることを考えよう。
dp(v) = 1+ avg(dp(e))
を小さくしたいので、dp(e)が最大となる辺を消すのが最適であることがわかる。
(なお、行先が2個以上ない頂点は削除できない点に注意)

よって、辺の削除をO(N)回程度行い、その都度DPの値をO(M)で埋めればO(NM)で解を求めることができる。
以下はO(NM)で通るか心配だったので、削除する辺より手前の頂点のみ値を再計算するようちょっと工夫しているが、要らなかった様子。

int N,M;
vector<int> E[606];
double dp[606],dp2[606];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
	}
	
	for(i=N-2;i>=0;i--) {
		FORR(e,E[i]) dp[i]+=1+dp[e];
		dp[i]/=E[i].size();
	}
	
	FOR(i,N) dp2[i]=dp[i];
	
	double ret=dp[0];
	for(i=N-2;i>=0;i--) if(E[i].size()>=2) {
		vector<double> V;
		FORR(e,E[i]) V.push_back(dp[e]);
		sort(ALL(V));
		V.pop_back();
		
		dp2[i]=0;
		FORR(v,V) dp2[i]+=1+v;
		dp2[i]/=V.size();
		
		for(j=i-1;j>=0;j--) {
			dp2[j]=0;
			FORR(e,E[j]) dp2[j]+=1+dp2[e];
			dp2[j]/=E[j].size();
		}
		ret=min(ret,dp2[0]);
		

		
		for(j=i;j>=0;j--) dp2[j]=dp[j];
	}
	
	_P("%.12lf\n",ret);
}

まとめ

Nの上限600って割と珍しいよね。