Educational Codeforces Round 117 (Rated for Div. 2) E. Messages

Problem - E - Codeforces

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을 곱한 값을 비교해 주면 된다.