Codeforces Round #577 (Div. 2) 회고

Codeforces Round #577 (Div. 2)

Dashboard - Codeforces Round #577 (Div. 2) - Codeforces

새벽 1시 30분에 열린 Codeforces였다. 졸려서 조금 퍼포먼스가 많이 떨어진 것도 있지만 요 전에 레이팅이 굉장히 많이 떨어졌기 때문에 2문제만 늦게 풀어도 레이팅이 오르더라..

 

A. Important Exam

$N$명의 학생들이 $M$개의 문제를 푸는데, 정답이 공개되지 않은 상황에서 어떻게 정답 처리를 해야 학생들의 점수 합이 최대가 되는지 묻는 문제였다.

당연하게, 각 문제마다 학생들이 가장 많이 답한 문제를 정답으로 처리하면 되는 쉬운 문제였다. 주어진 배점과 각 문제마다 optimal한 정답을 답한 학생들의 수를 곱해준 다음, 답을 출력하면 되는 문제였다.

굉장히 쉬운 문제였는데 뭔가 엄청난 착각을 해서 구현에 많은 시간이 걸렸던 것 같다. 대회 시작 16분만에 AC

 

B. Zero Array

$a_1, a_2, a_3, ... , a_n$이라는 수열이 있을 $a_i, a_j$를 선택해서 Operation 한 번에 \(a_i\)와 \(a_j\)를 각각 1씩 감소시킬 수 있다고 한다.

이 때, 주어진 배열을 모두 0으로 만들 수 있는가? 에 대한 문제였다.

수학적으로 생각해보면 정말 간단한 문제였는데

 1. 일단 한 번에 줄어들 수 있는 숫자의 합이 2이므로 배열의 합이 홀수인 경우는 절대 안된다.

 2. 모두 0으로 만들어야하므로 큰 수부터 줄여 나가는 전략이 유리한데, 만약 그 큰 수가 너무 큰 수라면 어떻게 되는가?

ex)

4

1 1 100 50

 분명히 합이 짝수인 짧은 예제이지만, 3번째 원소인 100을 무슨 짓을 해도 없앨 수 없다. 즉, 가장 큰 원소를 제외한 나머지 원소의 합이 가장 큰 원소보다 크면 무조건 지울 수 있다는 말이다. 짧게 Greedy한 Solution을 제출했고 AC를 받았다.

C. Maximum Median

\(a_1, a_2 , ... , a_n\)라는 수열이 있을 때, 한 원소를 골라 1을 증가시키는 operation을 할 수 있다고 한다. 이 Operation을 최대 K번 할 수 있다고 할 때, 이 수열의 median(중앙값)의 최대값을 구하라는 문제였다.

 

이 문제는 pretest 6번에서 WA를 받아 계속 통과하지 못했는데. 정해를 보니 binary search를 하는 문제였다.

 

내가 푼 방법은, 어차피 median을 최대화 하려면 median을 포함한 이후의 값만 증가시켜주면 되므로 상관 없다. 하지만, median만 증가시키면 자동으로 median이 언젠간 바뀔 것이므로 결국 median 뒤의 숫자들을 전부 증가시켜줘야한다.

 

그래서, $a[n-1]$부터 시작해 다음의 연산을 반복했다.

• $a[mid]~a[n-1]$까지 K번 연산 안에  [ mid, n-1 ]의 값을 a[n-1]로 바꿀 수 있는가? 
• 만약 그렇다면, K 에서 Sigma{n-1, i=n/2}(a[n-1]-a[i])를 해주고 a[n/2]부터 a[n-1]까지 모든값이 같으므로, 이 길이에 모두 1씩 더해주는 연산을 K가 0이될때까지 반복하면 된다. 즉, a[n/2]~a[n-1]의 원소에 K/(n-mid)를 해주면 된다.
• 만약 그렇지 않다면, a[mid] ~ a[n-2]까지 K번 연산 안에 [ mid, n-2] 의 값을 a[n-2]로 바꿀 수 있는가? 에 대한 질문의 답이다.
• 이 이후로는 위의 과정을 반복해주면 된다

하지만 WA를 받았다... 왜인지는 조금 더 반례를 찾고 싶다.

 

정해는 Binary Search를 사용해 $O(NlgN + (n/2)log(10^9))$였는데 결국 $O(NlogN)$의 풀이 방법이다.

즉, $l=0, r=10^9$로 두고 $m = (0+10^9)/2$로 둔 다음, $ \sum_{i=n/2}^{N} max(0, x-a_{i})$ 이 $K$가 넘지 않는 $x$를 찾는 문제이다.

되게 깔끔하게 풀 수 있는 문제였다. 몇년 전 부터 문제 풀 때 binary search를 쓰는 걸 항상 잊어버리는데 좀 주의해야겠다. 

 

개인적으로 이번 라운드는 ABC까지는 나쁘지 않은 문제들이었다고 생각하는데, D번 이후로는 좀 그렇지 않다는걸 느꼈다.