読者です 読者をやめる 読者になる 読者になる

AOJ2301 Sleeping Time

解答
K = 30 までで O(2^K) なので、多少枝刈りすれば通るだろうと思っていたが TLE がなかなか取れなかった。

決め手は solve() 関数内の 2行目の枝刈り。条件式を満たすとき今の確率を P倍 と (1-P)倍 に分割する必要がなくなる。

コメントアウトしてある条件式は、枝刈りで苦悩した軌跡。確率が 0 に近くなれば弾くという考えばかりが頭を走っていた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
int K;
double R, L;
double P, E, T;
 
#define EPS (1e-5)
 
typedef long long ll;
 
double solve(int const kcnt, double ll, double rr, double prob) {
  if(T+E < ll || rr+E < T) return 0.;
  if(abs(ll-T) <= E && abs(rr-T) <= E) return prob;
  //if(prob*pow(max(1.-P, P), K-kcnt)*pow(2., K) < EPS) return 0.;
  //if(prob*pow(max(1.-P, P), K-kcnt) < EPS) return 0.;
   
  double H = (ll + rr) / 2.;
   
  if(kcnt == K) {
    if(abs(H - T) <= E) {
      return prob;
    }
    else {
      return 0.;
    }
  }
   
  // step 3.
  double ret = 0.;
  if(H <= T) {
    ret += solve(kcnt+1, H, rr, prob*(1.-P));
    ret += solve(kcnt+1, ll, H, prob*P);
  }
  else {
    ret += solve(kcnt+1, ll, H, prob*(1.-P));
    ret += solve(kcnt+1, H, rr, prob*P);
  }
   
  return ret;
}
 
int main() {
   
  cin >> K >> L >> R;
  cin >> P >> E >> T;
   
  printf("%.7f\n", solve(0, L, R, 1.));
   
  return 0;
}