典型かな。
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); }
まとめ
これ系二分探索で解くってのは覚えたけど、大小関係にいつも戸惑う。