CF 712 E - Memory and Casinos
問題
問題概要
個のカジノが一列に並んでいる(左から番目のカジノをカジノと呼ぶ)。カジノで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はである。負けると1つ左に移動する(勝率は)。番目の左側と番目の右側は出口である。
また、区間に対して、次の条件を満たしている時、区間をdominate
すると呼ぶ:
- 番目のカジノからスタートする。
- 番目のカジノでは絶対に負けない。
- 番目のカジノで勝ち、右に移動して終了する。
次の2種類のクエリを考える:
- クエリ1 : が与えられるので、をにセットする。
- クエリ2 : が与えられるので、区間を
dominate
できる確率を答える。
以上のクエリが合計で個与えられるので順に処理せよ。
- どの状況でも、が成り立つ。
アイデア
区間を管理するために、SegmentTreeを使って高速に処理することを考える。区間のマージをどうするかを考える。
この上の2つの確率を定義して、区間と区間をマージして区間の結果を得ることを考える。とおくと、この4つを使っての値を表すことが出来る。
まず、を求める。これは、との間を何回またぐことになるかで場合分けをすることが出来る。1回またぐのは、ストレートに両区間でdominate
できれば良いのでとなる。次は、3回またぐパターンだが、これは([i,k]をdominate) → ([k+1,j]でdominate失敗) → ([i,k]でkスタートで耐えてk+1へ) → ([k+1,j]でdominate)
という流れになる。この確率は、である。以降またぐ回数が5, 7, 9, ... 回と無限に続き、これは初項、公比の無限等比級数であるから、である。
次に、を求める。これも上で考察したことと同様に、との間を何回またぐことになるか(0, 2, 4, 6, ...回)で場合分けをすることが出来る。0回のときだけは特別で、で、2回以降は初項、公比の無限等比級数であるから、である。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second using pd = pair<double, double>; struct SegTree{ int n; vector<pd> dat; //初期化 SegTree(int _n){ n=1; while(n<_n) n*=2; dat=vector<pd>(2*n-1,{1,0}); } pd merge(pd l, pd r){ double x1 = l.fi, y1 = l.se; double x2 = r.fi, y2 = r.se; double X = x1*x2 / (1 - y1*(1-x2)); double Y = y2 + (1-y2)*y1*x2 / (1 - (1-x2)*y1); return {X,Y}; } //k番目(0-indexed)の値をaに変更 void update(int k, double a){ k+=n-1; dat[k] = {a,a}; //更新 while(k>0){ k=(k-1)/2; dat[k]=merge(dat[2*k+1],dat[2*k+2]); } } //内部的に投げられるクエリ pd _query(int a, int b, int k, int l, int r){ if(r<=a || b<=l) return {1,0}; if(a<=l && r<=b) return dat[k]; pd vl=_query(a,b,2*k+1,l,(l+r)/2); pd vr=_query(a,b,2*k+2,(l+r)/2,r); return merge(vl,vr); } //[a,b) pd query(int a, int b){ return _query(a,b,0,0,n); } }; int main(){ int n,q; scanf(" %d %d", &n, &q); SegTree st(n); rep(i,n){ int a,b; scanf(" %d %d", &a, &b); st.update(i, (double)a/b); } while(q--){ int t; scanf(" %d", &t); if(t==1){ int i,a,b; scanf(" %d %d %d", &i, &a, &b); --i; st.update(i, (double)a/b); } else{ int l,r; scanf(" %d %d", &l, &r); --l; --r; printf("%.10f\n", st.query(l,r+1).fi); } } return 0; }