Sleeping Time
コード

難易度Blue 350 (非公式難易度表)

「k回の睡眠でR=r, L=lとした時のPP」を返す関数retを考えて、深さ優先探索を行う発想は自然。
だが、これだけでは2^30で計算が間に合わない。

なので、l, rとP, Eの関係に枝刈り条件を加える。
ret内のl-rを呼び出し回数に関して指数関数的に収束させていくので、この条件はかなり強い枝刈りが可能である。

#include <iostream>
#include <cstdio>
using namespace std;
#define abs(a) ((a) > 0 ? (a) : -(a))
 
double P, E, T;
double ret(double k, double r, double l)
{
    double h = (r + l) / 2;
    if (k == 0) 
        return (abs(h-T) < E ? 1.0 : 0.0);
    if (l < T - E)
        return 0.0;
    if (r > T + E) 
        return 0.0;
    if (T - E < r && l < T + E) 
        return 1.0;
    if ((r+l)/2 >= T) 
        return P * ret(k-1, r, h) + (1.0 - P) * ret(k-1, h, l);
    else
        return P * ret(k-1, h, l) + (1.0 - P) * ret(k-1, r, h);
}
 
int main(void)
{
    double K, R, L;
    cin >> K >> R >> L >> P >> E >> T;
    P = 1 - P;
 
    printf("%.6f", ret(K, R, L));
    return 0;
}