aoj 2301 - Sleeping Time

問題

問題概要

LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。

解法

全探索で、やろうと思うと、2^k(k=30)でTLE??
ただし、2分探索をしていく途中で、
(T - E <= l && r <= T + E)となると、そのあと確率Pでも(1-P)でも、hはEの誤差範囲入り、
(r < T - E || T + E < l)となると、そのあと確率Pでも(1-P)でも、hはEの誤差範囲内に入ることはないため、そのあとの確率が一意に決まり、枝刈りができることになり、dfsを行う再帰関数を早い段階で切ることができる。

ミス

LとRが逆なの怖すぎでしょｗｗ

コード

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

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

double solve(double l, double r, double k){
    double h = (l + r) / 2;

    if(k == K){//k回二分探索した後の結果
        if(abs(h - T) < E) return 1.0;
        else return 0.0;
    }

    //枝狩り
    //この後どうやって二分探索しても絶対時誤差がEの範囲に収まる
    if(T - E <= l && r <= T + E) return 1;
    //この後どうやって二分探索しても絶対時誤差がEの範囲に収まらない
    if(r < T - E || T + E < l) return 0;

    double tmpp = 0;//確率の合計(独立事象なので和)
    if(h >= T){//時間が長すぎる
        tmpp += (1 - P) * solve(l, h, k + 1);//correct
        tmpp += P * solve(h, r, k + 1);//mistake
    }else{//時間が短すぎる
        tmpp += (1 - P) * solve(h, r, k + 1);//correct
        tmpp += P * solve(l, h, k + 1);//mistake
    }
    return tmpp;
}

int main(void){
    cin >> K >> R >> L >> P >> E >> T;
    swap(R, L);
    printf("%.9f\n", solve(L, R, 0));
    return 0;
}