AOJ2301 Sleeping Time

Sleeping Time | Aizu Online Judge

Miki is a high school student. She has a part time job, so she cannot take enough sleep on weekdays. She wants to take good sleep on holidays, but she doesn't know the best length of sleeping time for her.

愚直に 回のシュミレーションに対して，間違う/間違わないをすると となる．ここで枝刈りを行う．シュミレーションが2分探索みたいな感じなので，一度解区間 を外れたら，再度解区間に入ることは無いので切って良い．この枝刈りだけで でACが取れた．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int k;
double p, e, t;

double ans = 0;

void dfs(double l, double r, int cnt, double x) {
  if(r < t - e) return;
  if(l > t + e) return;

  double h = (l + r) / 2;

  if(cnt == k) {
      if(t - e <= h && h <= t + e) ans += x;
      return;
  }

  if(h >= t) {
      dfs(l, h, cnt + 1, (1.0 - p) * x);
      dfs(h, r, cnt + 1, p * x);
  } else {
      dfs(h, r, cnt + 1, (1.0 - p) * x);
      dfs(l, h, cnt + 1, p * x);
  }
}

int main() {
  double l, r;
  cin >> k >> l >> r;
  cin >> p >> e >> t;

  dfs(l, r, 0, 1.0);

  cout << fixed;
  cout.precision(20);
  cout << ans << endl;

  return 0;
}

しかし，他の人の解答を見てみるとばかりだった．自分の解法は が十分小さい時に有効な枝刈りで， が大きい場合を考えていなかった． この時は解区間が探索区間を内包しているので，この先解区間を出ることはない．よってその枝刈りを追加すると とめちゃくちゃ早くなった．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int k;
double p, e, t;

double ans = 0;

void dfs(double l, double r, int cnt, double x) {
  if(r < t - e) return;
  if(l > t + e) return;
  if(t - e <= l && r <= t + e) {
      ans += x;
      return;
  }

  double h = (l + r) / 2;

  if(cnt == k) {
      if(t - e <= h && h <= t + e) ans += x;
      return;
  }

  if(h >= t) {
      dfs(l, h, cnt + 1, (1.0 - p) * x);
      dfs(h, r, cnt + 1, p * x);
  } else {
      dfs(h, r, cnt + 1, (1.0 - p) * x);
      dfs(l, h, cnt + 1, p * x);
  }
}

int main() {
  double l, r;
  cin >> k >> l >> r;
  cin >> p >> e >> t;

  dfs(l, r, 0, 1.0);

  cout << fixed;
  cout.precision(20);
  cout << ans << endl;

  return 0;
}

まとめると，

  • が十分小さい時に，解区間から外れた場合の枝刈りが有効
  • が十分大きい時に，解区間が内包する場合の枝刈りが有効

となって， にはならないで間に合う．(どのくらい減るのかよく分かっていない)

May 21st, 2016
350, aoj-icpc