codeforces 335 E Counting Skyscrapers(확률 기대)

제목 링크
제목 번역
분석: 아아, 왜 라벨이 다 dp야?하지만 선배들은 이 문제가 전혀 dp가 아니라고 토로하는데...
선배가 O(n2h)O(n2h)의 dp가 있다고 하자 xue는 생각했다. f[i][k]f[i][k]는 i동까지 높이가 k일 때 Bob계수기의 기대 매거와 i가 연결된 건축물 j는 분명히 j~i 사이에 k보다 높은 건물이 없을 것이다. 확률은 (k-31)xhx, x=i-3j-3-1(k-3-1)xhx,x = i -3 j -3 1 (Bob은 h 이상의 높이에 도달할 수 없기 때문에 우리는 고려할 필요가 없다)
분명히 이 dp는 아무 소용이 없어요.

정해

우리는 여전히 얕은 것에서 깊은 것까지

Bob->Alice

우선 샘플을 살펴보자. 왜 출력된 정수가 리얼 형식이 아닌지. 마치 고양이 냄새가 나는 것 같아. (계산된 것 같지 않고 읽은 후 세계에서 출력된 것 같아) 실제로 AC 코드를 찾아서 시험해 보니 확실히 무슨 출력을 입력한 것 같아. 뭐야, 누군가처럼 투기하지 마. 우리는 증명할 수 있어.

Bob의 카운터가 2i 2i를 누적하면 그가 지나간 건물의 기대 수량도 2i 2i이다

불완전한 증명:
분명히 Bob은 ZIP 운송선을 한 번 사용할 때마다 실제로 지나가는 건물 수는 운송선 아래에서 높이가 비교적 작은 빌딩+종점 빌딩이다. 즉, 만약에 그가 ii동을 지나갔다면 i-3-1i-3동의 높이가 비교적 작은 빌딩이 사이에 있다는 것이다.
Bob을 설정하면 현재 계수기가 2H2H 증가하면 그는 H층에 있다. 그러나 이 zz의 번호 방식 때문에 H층의 높이는 사실상 H+1H+1이다. 그러면 그가 지나간 건물의 높이는 HH를 초과하지 않을 것이다.
빌딩의 기대 = 1\8727P(중간에 높이≤H가 없는 건물)\8727P(종점 건물의 높이≥H) 1\8727P(중간에 높이≤H가 없는 건물)\872727P(종점 건물의 높이≥H)+2\872727P(중간에 한 건물이 있고 높이≤H)\87878787P(종점 건물의 높이≥H)\8787P(종점 건물의 높이≥H)+2\872727P(중간에 한 건물이 있고 높이≤HH) P(중간에 한 건물이 있고 높이 ≤HH) VIP(종점 건물의 높이가 있고 2층 높이가 ≤H) VIP(종점 건물의 중간 높이가 있고 2층은 2층 높이가 있고 2층 높이가 있고 2층 사이에 두 건물의 높이가 있고 2층 사이에 두 건물의 높이가 있다. H) P(종점의 높이≥H)+...+∗P(중간에 두 동, 높이≤H) 𕓭P(종점의 높이≥H)+.(PP는 확률을 나타낸다)
제목에서 높이가 ii인 건물이 나타날 확률은 2 - i = (12)i 2 - i = (12)i
따라서 한 건물의 높이가 ≤H≤H일 확률:
P=(12)1+(12)2+(12)3+...+(12)H P = ( 1 2 ) 1 + ( 1 2 ) 2 + ( 1 2 ) 3 + . . . + ( 1 2 ) H
P=(12)H+1−1212−1 P = ( 1 2 ) H + 1 − 1 2 1 2 − 1
P=2H−12H P = 2 H − 1 2 H
기대:
E=1∗P0∗(1−P)+2∗P1∗(1−P)+3∗P2∗(1−P)+... E = 1 ∗ P 0 ∗ ( 1 − P ) + 2 ∗ P 1 ∗ ( 1 − P ) + 3 ∗ P 2 ∗ ( 1 − P ) + . . .
E=(1−P)∗(1∗P0+2∗P1+3∗P2+...) E = ( 1 − P ) ∗ ( 1 ∗ P 0 + 2 ∗ P 1 + 3 ∗ P 2 + . . . )
혼합 등차 등비 수열, 오차 상쇄:
E=(1−P)∗(1∗P0+2∗P1+3∗P2+...)① E = ( 1 − P ) ∗ ( 1 ∗ P 0 + 2 ∗ P 1 + 3 ∗ P 2 + . . . ) ①
P∗E=(1−P)∗(1∗P1+2∗P2+3∗P3+...)② P ∗ E = ( 1 − P ) ∗ ( 1 ∗ P 1 + 2 ∗ P 2 + 3 ∗ P 3 + . . . ) ②
① - ②, 득:
(1−P)∗E=(1−P)∗(P0+P1+P2+...) ( 1 − P ) ∗ E = ( 1 − P ) ∗ ( P 0 + P 1 + P 2 + . . . )
E=11−P E = 1 1 − P
여기서,
P=2H−12H P = 2 H − 1 2 H
E=2H E = 2 H

Alice->Bob

우선 모든 건물이 1층이고 번호가 0이라고 가정하자면Bod의 계수기는 반드시 nn을 얻는다
이후에 우리는 높이가 더 높은 층을 추가해야 한다. 그러면 층 사이에 ZIP 운송선이 나타날 것이다. 이때 Bob계수기의 답은 운송선의 공헌-덮어버린 건물의 공헌이다.
우리는 1층 1층으로 건물을 높인다. 새로 가입한 번호가 HH에 도달할 수 있는 이 두 건물의 번호는 각각 i, j, j, L=j-3 i L=j-3 i이다. 만약에 이 두 건물의 H층 사이에 운송선이 있다면 반드시 만족해야 한다. i i와 j의 높이≥H+1≥H+1,i-3 j i -3 j 사이의 빌딩의 높이가 H보다 작으면 H보다 작기 전에 우리는 이미 한 건물의 높이≤ H≤ H의 확률을 구했다. P=2H -3 12H P = 2H -3 12H H 명백하다. 한 건물의 높이≥H+1 ≥H + 1의 확률: 1-3 P=12H 1:1
따라서 두 층의 번호가 HH에 도달할 수 있는 건물 중간에 하나의 운송선이 존재할 확률이 있다.
(1−P)2∗PL−1=(12H)2∗(2H−12H)L−1=(12H)2∗(1−12H)L−1 ( 1 − P ) 2 ∗ P L − 1 = ( 1 2 H ) 2 ∗ ( 2 H − 1 2 H ) L − 1 = ( 1 2 H ) 2 ∗ ( 1 − 1 2 H ) L − 1
우리는 층층이 계산했기 때문에 H - 1 H - 1 층의 운송선만 남아서 영향을 없애지 못했다
그렇다면 이런 운송선이 존재한다는 것을 알았다면, 중간에 얼마나 많은 낡은 로프가 덮여 있었을까?

분명히 최대 층수가 H -3 1 H -3 1이고 높이가 H H인 탑의 수량은 +1이다

그럼 HH 높이에 딱 맞는 건물의 기대수만 있으면 돼요.
여기의 계산에 주의할 수 있는 조건이 하나 있다. 중간의 L-3-1L-3 1동의 높이는 반드시 HH를 초과하지 않는다. 아래에서 확률 공식으로 계산하는 것을 고려하면 공식이 있다(B조건이 성립된 전제에서 AA가 발생할 확률)
P(A|B)=P(A∩B)P(B) P ( A | B ) = P ( A ∩ B ) P ( B )
그 중
A=빌딩의 높이는 H A=빌딩의 높이는 H이다.
B=빌딩의 높이는 H를 넘지 않는다 =빌딩의 높이는 H를 넘지 않는다
분명히
P(A∩B)=P(A)=12H P ( A ∩ B ) = P ( A ) = 1 2 H
P(B)=2H−12H P ( B ) = 2 H − 1 2 H
그러면 한 건물의 높이는 꼭 알맞다
H H의 확률은
12H∗2H2H−1=12H−1 1 2 H ∗ 2 H 2 H − 1 = 1 2 H − 1
= 1\8727P(L: 1동의 높이가 모두 H 이하) 기대 = 1𕓭P(L: 1동의 높이가 H 이하)+2𕓭P(1동의 높이가 H) + 2\87277P(L: 2동의 높이가 H 이하) + 2𕓭P(1동의 높이가 H)\87277P(L: 2동의 높이가 H) 𕓭P(L: 2동의 높이가 모두 H) + 3동의 높이보다 작다)+3\87P(L: H) + 2동의 높이가 모두 기대 이하) + 3동의 높이보다 작다 = 1\87P(H 기대 기대 = 1\87P)) + 3∗P(두 건물의 높이는 H) ∗P(L -3동 모두 H 미만) +...+L∗P(L -3 1동의 높이는 H) +.L∗P(L -3 1동의 높이는 H)
E=1∗(1−12H−1)L−1+2∗12H−1∗(1−12H−1)L−2+...+L∗(12H−1)L−1 E = 1 ∗ ( 1 − 1 2 H − 1 ) L − 1 + 2 ∗ 1 2 H − 1 ∗ ( 1 − 1 2 H − 1 ) L − 2 + . . . + L ∗ ( 1 2 H − 1 ) L − 1
E=1+L−12H−1 E = 1 + L − 1 2 H − 1
각 길이의 LL에 대해 현재 층에 N-L-N-L의 가능한 위치에 로프가 존재한다. 그러면 먼저 높이를 매거한 다음에 LL을 매거한다. 위의 추측을 종합하면 우리는 다음과 같은 계산식을 얻을 수 있다.
n+∑i=1h∑j=1n(n−j)∗(12i)2∗(1−12i)j−1∗(2i−2i−1∗(1+j−12i−1)) n + ∑ i = 1 h ∑ j = 1 n ( n − j ) ∗ ( 1 2 i ) 2 ∗ ( 1 − 1 2 i ) j − 1 ∗ ( 2 i − 2 i − 1 ∗ ( 1 + j − 1 2 i − 1 ) )
두 층의 번호가 HH에 도달할 수 있는 건물 중간에 하나의 운송선이 존재할 확률: (12i)2∗(1-32i)j-1(12i)2∗(1-12i)j-1층수는 i의 운송선 공헌: 2i2i가 줄여야 할 덮인 운송선 공헌: 2i-12i-1층수는 i-1(덮인)i-1i-1(덮인)운송선의 기대: 1+ji-1-2i-1-1-1-2i-1
이 식은 O(nh) O(nh)의 복잡도로 완성할 수 있다. 다다들은 내부는 행렬 곱셈으로 최적화된 다음에 O(hlogn) O(hl o g n)의 복잡도에 도달할 수 있음을 나타낸다.

tip

이 문제는 정말 광속 요법이다
정부측 문제풀이.

#include
#include
#include

using namespace std;

char s[10];
int n,h;
double mi[200];

double KSM(double a,int b) {
    double t=1.0;
    while (b) {
        if (b&1) t=t*a;
        a=a*a;
        b>>=1;
    }
    return t;
}

int main() {
    scanf("%s",s);
    scanf("%d%d",&n,&h);

    if (s[0]=='B') {
        printf("%d
",n);
        return 0;
    }

    double ans=(double)n;
    mi[0]=1.0;
    for (int i=1;i<=2*h;i++) mi[i]=mi[i-1]*2.0;
    for (int i=1;i<=h;i++)
        for (int j=1;j<=n;j++) {
            double t=KSM(1.0-1.0/mi[i],j-1);
            ans+=1.0*(n-j)*(1.0/mi[2*i])*t*(mi[i]-mi[i-1]*(1+(double)(j-1)/(mi[i]-1.0)));
        }
    printf("%.10lf
",ans);

    return 0;
}