lsc4719   1년 전

http://codeforces.com/contest/...  문제 url

http://codeforces.com/blog/ent... 에디토리얼 url

에디토리얼 글에서 E번을 보시면요, 댓글을 참고하면

inv(1, n) - inv(l, r) + (l-r+1)*(l-r) / 2 = segment [l, r]의 # of expected inversions인 것 같은데요, 

왜 이 등식이 성립하는지 그 이유를 모르겠습니다. 알려주세요!

---

문제를 설명드리면요.

lsc4719   1년 전

문제는,

(1, 2, ..., n)의 임의의 permutation S가 입력으로 주어집니다. 이 때, n < 100000 입니다.

S에 대해 3가지 연산을 순서대로 적용합니다.

연산1. 임의의 l<=r에 대해 동일한 확률로 S[l..r]을 고릅니다. (S[l..r]은 S = (s1, s2, ..., sn)이라 할 때, S[l..r] = (sl, s(l+1), ..., sr)입니다.)

연산2. 연산 1에서 고른 S[l..r]의 임의의 permutation P를 동일한 확률로 고릅니다. P = (p1, p2, ..., p(r-l+1))

연산3. S에서 S[l..r]을 P로 대체합니다.

위의 세 연산을 순서대로 S에 적용한다고 할 때,

연산을 마친 후 S가 가진 inversion의 갯수의 기댓값은 얼마일까요?

입니다. (inversion := i<j인데 S[i]>S[j]인 경우)

jseo   1년 전

연산 3을 적용한 길이 n인 구간의 inversion 기대값은 n(n - 1) / 4입니다. 

I_{i, j} 를 구간의 i번째 원소와 j번째 원소가 inversion이면 I_{i, j} = 1, 아니면 I_{i, j} = 0인 RV라고 했을때 E[I_{i, j}] = 1 / 2 란걸 알수 있습니다 (symmetrical 하기 때문)

기대값의 선형성에 의해 다 더해보면 n(n - 1) / 2 * 1 / 2 = n(n - 1) / 4죠.

그러므로 구간 [l, r]을 선택했을때 inversion 기대값은 inv(1, n) - inv(l, r) + (l - r + 1) * (l - r) / 4가 되는겁니다. 

lsc4719   1년 전

구해야 하는 답은 이해가 되었습니다.

:) :) :)

이제 빠르게 계산하는 법만 알아내면 될 것 같습니다.

감사합니다:):))

lsc4719   1년 전

위에 설명하신 것에서 "연산 3" -> "연산 2" 이죠?

댓글을 작성하려면 로그인해야 합니다.