Codeforces #901 : Div1 D. Jellyfish and Miku

時間がかかったけどどうにか解けて良かった。
https://codeforces.com/contest/1874/problem/D

問題

正整数N,Mが与えられる。
点0～点Nの計(N+1)点が順にN本の無向辺でつながれたグラフを考える。
今各辺に正整数の重みを、合計がM以下となるように振る。

今点0に駒を置く。
そこから、つながれた辺の重みに比例した確率で、駒を辺に沿って動かす。
重みを最適に振ったとき、駒の移動回数の期待値の最小値を求めよ。

解法

dp(n,m) := n点に至るまでの辺にmまでの重さを振ったとき、戻る方向に駒を移動する回数の最小値
とすると、解はdp(N,M)*2+Nである。あとはdp(n,m)の埋め方を考える。

実験すると、
dp(n+1,m+c) = min(dp(n,m)+m/c)
で計算できることがわかる。
n,m,cを総当たりすると一見O(N^2*M)ぐらいかかるが、辺の重さは単調増加となるように振るのがいいので、cの範囲はかなり狭くなり、間に合う。

int N,M;

double from[3030];
double to[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	if(N==1) {
		cout<<1<<endl;
		return;
	}
	
	FOR(x,3030) from[x]=1e10;
	from[1]=0;
	for(i=2;i<=N;i++) {
		FOR(x,3030) to[x]=1e10;
		for(x=M;x>=i-1;x--) if(from[x]<1e10) {
			for(y=x/(i-1);x+y*(N+1-i)<=M;y++) {
				chmin(to[x+y],from[x]+1.0*x/y);
			}
		}
		swap(from,to);
	}
	double ret=from[M]*2+N;
	_P("%.12lf\n",ret);
}

まとめ

自分は実験で解いたけど、これ式変形とかで短時間で出せるのかな。