aoj2301:Sleeping Time

問題文

Sleeping Time | Aizu Online Judge

解法

高さがK+1のセグツリー上を歩く問題と考えることができる。
「あのあたりに行きたい」みたいな範囲(T-E～T+E)があって、そこに行くことに成功する確率を求める。
確率(1-P)でいい感じの方向に行って、確率Pでやばい方向に行く。
現在l～rを見ているとして、T-E<=lかつr<=T+Eなら確実に成功する。
また、T+E < lまたはr < T-Eならば確実に失敗する。

遷移に関するいろいろな条件がセグツリーそのものなので、O(logN)頂点しか訪れない。

入力される変数をあらかじめ2^50倍しておけば、整数で誤差なく扱える。
・・・と思ったが、EやTが有限の桁数で2進表示できないときは誤差がでる。
でも通った(誤差とかについて考えるのが苦手なのでよくわからないが、2^50程度の数からすればちょっとずれても大した問題にはならないんだろうか)

あと、どうでもいいけど普通L<=Rだろ・・・と思った。こういう名前空間(?)を攻撃してくるタイプのあれはつらい

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int in(){
    double t;
    scanf("%lf",&t);
    return t*(1ll<<50);
}

int K,L,R;
double P;
int E,T;

int w;
int sl,sr;

double dfs(int k,int l,int r){
    if(k==K){
        int m=(l+r)/2;
        if(T-E<=m&&m<=T+E)return 1.0;
        else return 0.0;
    }
    if(r<T-E||T+E<l)return 0.0;
    if(T-E<=l&&r<=T+E)return 1.0;
    int m=(l+r)/2;
    if(m>=T)return (1-P)*dfs(k+1,l,m)+P*dfs(k+1,m,r);
    else return P*dfs(k+1,l,m)+(1-P)*dfs(k+1,m,r);
}

signed main(){
    scanf("%lld",&K);
    L=in();R=in();
    scanf("%lf",&P);
    E=in();T=in();

    printf("%.20f\n",dfs(0,L,R));
    return 0;
}