https://www.acmicpc.net/problem/7686
문제 요약
- "누적 평균"을 정의하고, k개 이하로 제거 가능할 때, 가장 높은 누적 평균값을 구하기
- 누적평균은 (a, b)이루어진 순서쌍들이 있을때 a의 합은 분자, b의 합은 분모로 해서 나누는 것
- 이렇게 나눈 값을 "반올림" 한 값이 누적 평균
- 스탠포드 문제 같은데 다행히 테케가 있다 : https://cs.stanford.edu/group/acm/oldsite/SLPC2018/history.php
접근법 - DP, 실패
- 누적평균을 기울기로 보고 기울기가 큰 것에 이어 붙이면 커질 것이다로 접근해 보았다.
- 즉 dp[x] = x개를 이용해서 만들 수 있는 가장 큰 기울기로 정의하고
- dp[x + 1] = max{dp[x] + (a, b) : +는 분자/분모 더하기 연산}
- 맞는 것처럼 보이나 결정적인 오류가 있었음
- 입력의 순서만 바뀌어도 값을 보장할 수 없음
- 이유는 기울기만 보는 것이 아니라 분자/분모의 크기도 봐야함
- 0/1, 1/100000 에서 당연히 1/100000이 기울기가 크고 여기에 이어붙이는게 유리할 것 처럼 보이지만
- 0/1 + 1/1 = 1/2, 1/100000 + 1/1 = 2/100001
- 즉 기울기만으로는 올바른 답을 구할 수 없음
접근법 - 이분탐색, 공식해설 참고함
- sum(a) / sum(b) >= x라고 하면
- sum(a) >= x * sum(b)
- sum(a) - x(sum(b)) >= 0
- (a1-xb1) + (a2-xb2) + ... >= 0
- 최대 k개를 제거해서 이 조건을 만족시키려면 큰 것부터 가져가면됨
- 여기에서 반올림 처리를 위해서 추가 작업을 해야함
newbieski