kmjp's blog

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

AtCoder ABC #189 : F - Sugoroku2

典型かな。
https://atcoder.jp/contests/abc189/tasks/abc189_f

問題

1マスが1列に並んだ双六を考える。
さいころの目は1~Mのいずれかが等確率で出る。
0番のマスから初めて、N番以降のマスに到達すると上りとなる。
ただし、途中K個だけ振り出しに戻るマスがある。

上りまでにさいころを振る回数の期待値を求めよ。

解法

f(i) := 今i番目のマスにいるとき、上りまでに必要なさいころを振る回数の期待値
とする。振り出しに戻るがなければこれは容易で、

  • i≧Nならf(i)=0
  • i<Nの時、f(i) = 1 + avg(f(i+1)....f(i+M))

なので、累積和を使いながらiの大きい順に計算し、f(0)を答えればよい。

では振り出しに戻るマスがある場合どうするか。
x番のマスがそのようなマスである場合、f(x)=f(0)となる。
ただ求めたいのがそのf(0)なので、結局f(x)をどうすればよいかわからない。

そこでf(0)=yを仮置きすることを考える。f(x)=yとして上記手順でf(0)を求めたとき、結果的にf(0)>yとなると、f(0)の見積もりが少なすぎたということになる。
その場合f(0)をもっと大きくすべきだったということになる。
そこで、yを二分探索し、f(0)≦yとなる最大のf(0)を求めよう。

類題としてはARC016がある。
D - 軍艦ゲーム

int N,M,K;
int A[101010];
int NG[101010];
long double dp[202020],S[202020];

long double hoge(double v) {
	int i;
	
	for(i=N-1;i>=0;i--) {
		if(NG[i]) {
			dp[i]=v;
		}
		else {
			dp[i]=1+(S[i+1]-S[i+1+M])/M;
		}
		S[i]=S[i+1]+dp[i];
	}
	return dp[0];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	int p=-1,cur=0;
	FOR(i,K) {
		cin>>A[i];
		if(p+1!=A[i]) cur=0;
		p=A[i];
		NG[A[i]]=1;
		cur++;
		if(cur==M) return _P("-1\n");
	}
	
	long double L=0,R=1e12;
	FOR(i,300) {
		long double M=(L+R)/2;
		if(hoge(M)>M) L=M;
		else R=M;
	}
	_P("%.12lf\n",(double)L);
	
}

まとめ

これ系二分探索で解くってのは覚えたけど、大小関係にいつも戸惑う。