Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Graph Cost
- Div. 2
- vue3
- 알고리즘 대회
- 앳코더
- idpiframe_initialization_failed
- 리버싱
- dart
- 2022
- expand item
- Codeforces Round 831 (Div. 1 + Div. 2)
- Hello 2023
- 코드포스
- Good Bye 2022: 2023 is NEAR
- Round 866
- 인하대 프로그래밍 경진대회
- 밑바닥부터 시작하는 딥러닝 1
- list_display
- django
- shake!
- 기본키 변경
- 레지스터
- vue-google-login
- Flutter
- iupc
- 카카오 로그인
- E - Hanging Hearts
- 카카오 API
- 넥토리얼
- 1557
Archives
- Today
- Total
pseong
Educational Codeforces Round 117 (Rated for Div. 2) E. Messages 본문
알고리즘/알고리즘 문제풀이
Educational Codeforces Round 117 (Rated for Div. 2) E. Messages
pseong 2022. 6. 27. 19:54Problem - E - Codeforces
codeforces.com
k가 최대 20개 까지니까 고정할 메시지를 개수를 1부터 20개 중 최적의 하나를 선택하여 구성하면 된다.
고정할 메시지 개수를 t 개라고 하자. 이때 모든 메시지 번호에 기댓값을 부여할 수 있다.
메시지 번호를 기댓값 대로 정렬해 준 다음 큰 순서대로 메시지 t개를 선택한다.
그렇게 되면 고정할 메시지 개수 t개에 따른 전체 기댓값이 나오게 된다.
어떤 메시지 번호 x가 고정할 메시지 개수 t에 포함한다고 가정하자.
메시지 번호 x의 기댓값은 메시지 번호 x를 원하는 사람 i의 min(t, k[i]) 의 모든 합이다.
만약 k[i] 가 t개보다 작다면 메시지 x를 선택할 확률은 k[i] / t이다.
만약 k[i] 가 t개보다 크다면 메시지 x를 선택할 확률은 t / t이다.
모두 기댓값은 분모가 t라는 것을 확인할 수 있다.
분모가 같으므로 각 각의 메시지 번호를 기댓값 대로 정렬해서 그냥 더해도 괜찮다.
이렇게 특정 메시지 개수 t에 대해 기댓값과 t개를 구성한 메시지 번호를
t = 1부터 t = 20까지 전부 구해준다.
그중 최고 기댓값을 가진 t가 정답이 되는데 각 각은 분모가 다르므로 각 각 의 분모를 곱해서 비교해야 한다.
예를 들어 t = 3 일 때 기댓값이 50이고 t = 5일 때 기댓값이 70이라는 뜻은
50 / 3과 70 / 5를 비교해야 한다는 것이다. 분모를 3 * 5로 통분해 주면 된다.
50에 5를 곱한 값과 70에 3을 곱한 값을 비교해 주면 된다.
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
Comments