Codeforces #901 : Div1 C. Jellyfish and EVA

問題文がちょっと読みにくいな。
https://codeforces.com/contest/1874/problem/C

問題

DAGを成すグラフが与えられる。
今1番の点に車があり、2人で操縦している。

車の操縦は以下のように行われる。

• 2人は、現在いる頂点から延びる有向辺を選ぶ。1人は任意の辺を選ぶことが出来、もう一人は等確率でランダムに辺を選ぶ。
  • 2人の意見が一致した場合、その辺にそって車を移動する。
  • 一致しない場合、2人の選んだ辺を2つ削除し、また2人選び直す。途中辺がなくなったら、車はそれ以上動けない。

1人目が最適に辺を選んだ時、N番の点に車が移動できる確率を求めよ。

解法

頂点番号の大きい順に、N番の点に車が移動できる確率を求めよう。
1人目が辺を選ぶとき、N番の点に至る確率が多い点を優先的に選ぶのが良い。

dpで、すでにx回辺の破壊が発生し、y本あと壊さないといけない辺が残っている状態における確率を求めよう。

int T,N,M;
vector<int> E[5555];
vector<int> RE[5555];
double dp[5050];

double hoge(vector<double> D) {
	static double dp[5050][5050];
	int N=D.size();
	int i,j,x,y;
	FOR(i,N+2) FOR(j,N+2) dp[i][j]=0;
	dp[0][0]=1;
	double ret=0;
	FOR(x,N) {
		FOR(y,N) if(dp[x][y]) {
			int lef=N-x;
			if(y>=lef) continue;
			//壊された
			if(y) {
				dp[x+1][y-1]+=dp[x][y]*y/lef;
			}
			double can=dp[x][y]*(lef-y)/lef;
			//両方選択した
			ret+=can/(lef-y)*D[x];
			//ずれた
			dp[x+1][y+1]+=can*(lef-y-1)/(lef-y);
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			E[i].clear();
			RE[i].clear();
			dp[i]=0;
		}
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			RE[y-1].push_back(x-1);
		}
		dp[N-1]=1;
		for(i=N-2;i>=0;i--) if(E[i].size()) {
			vector<double> D;
			FORR(e,E[i]) D.push_back(dp[e]);
			sort(ALL(D));
			reverse(ALL(D));
			dp[i]=hoge(D);
		}
		_P("%.12lf\n",dp[0]);
	}
}

まとめ

これは割とすんなり。実際Bよりも短い時間で解けたし、全体のAC数もBよりCの方が多いね。