[일반] 24272 도움

[익명(14.43)]

우선 미리 감사드립니다

기댓값의 선형성을 이용하여 이 값을 찾아야 하는거 까진 알겠는데 O(M)보다 빨리 이 값을 어떻게 구하나요?

[익명(223.39)]

문제 잘못적은듯

[익명(14.43)]

그러네요 ㅠㅠ 30393입니당

[나는최고(mebest)]

M의 크기가 너무 크기때문에 당연하지만 N개의 그룹별로 빠르게 기댓값을 구하는게 핵심인 문제겠네요

[나는최고(mebest)]

당장 생각해 봤을 때에는, 그룹에서 선발된 학생 수가 X라고 했을때 쌍의 개수는 X(X-1)/2 = X^2/2 - X/2, 즉 X의 기댓값과 X^2의 기댓값 두개를 계산할 수 있다면 순서쌍의 개수의 기댓값도 구할 수 있을 것 같아요

[익명(14.43)]

우선 제시해주신 방식으로 접근해보고 있는데 기댓값을 빠르게 계산하는 부분에서 또 막히네요...ㅜㅜ 힌트라도 주실 수 있으시면 감사하겟습니다

[나는최고(mebest)]

우선 X의 기댓값부터 생각해볼까요? M개를 하나하나 보는 방식으로는 문제를 풀 수 없고, 각 사람별로 뽑힐 확률은 M / S가 될텐데, 조금 쉽게 이해하기 위해 그냥 뽑힐 확률을 p라고 하겠습니다. 그러면 X의 기댓값은 해당 그룹의 인원을 n이라고 할 때 p * n이 되겠네요

[나는최고(mebest)]

X^2의 기댓값은.. 분산을 이용해서 구하는 편이 조금 더 쉽습니다 한번 더 고민해보세요

[익명(14.43)]

도움 너무 감사드립니다 지금은 문제가 요구하는 사전지식이 부족한거 같고 확률론을 더 공부해보고 다시 도전해볼게요

[나는최고(mebest)]

[익명(14.43)]

덕분에 해결햇습니다 정말 감사합니다

[나는최고(mebest)]