대회후기: Codeforces Round #618 (Div. 2)

몰아쓰는 후기 #1

---

A: Non-zero

정수의 배열이 있다. 배열의 한 원소에 1을 더하는 것을 하나의 operation으로 정의할 때, 배열의 sum과 product가 모두 0이 아니기 위해서 필요한 operation의 최소 횟수를 구해야 한다.

Product가 0이 되지 않기 위해서는 배열 내의 0들을 우선 치워야 한다. 1씩 더해서 치운 후에 배열의 sum이 0이 아니라면, 아무 곳에서 1을 얹어주면 될 일이다.

5분에 AC

---

B: Assigning to Classes

주어진 숫자들을 두 그룹으로 나누어 각 그룹의 median의 차이를 최소화해야 한다.

모든 숫자들을 정렬해 나열해놓고, 그 중에서 두번째 그룹의 median값으로 만들고자 하는 숫자를 정하고, 방금 정한 median값의 좌우로 하나씩 두번째 그룹에 포함시킬 원소들을 선택하는 상황을 생각해보면, 무조건 median이 될 한 숫자만을 뽑는 것이 median의 차이를 최소화시키는 선택이라는 것을 알 수 있다.

따라서 $O(n\log n)$정렬 후 $O(n)$으로 두번째 그룹에 속할 원소를 iterate하며 최솟값을 찾으면 된다.

18분에 AC

한 단계 더 생각한다면 그냥 정렬 후 가운데 두 값의 차이를 출력하면 된다는 것을 확인할 수 있다.

---

C: Anu Has a Function

음이 아닌 정수를 정의역과 공역으로 갖는 함수 $f: f(x, y)=(x|y)-y$가 있다. 음의 아닌 정수로 이루어진 배열이 들어올 때, [배열 가장 앞의 두 원소를 $x$, $y$를 pop하고 $f(x, y)$를 배열의 앞쪽에 push하는 과정]을 배열에 원소가 하나 남을 때까지 반복했을 때, 그 남은 하나의 원소의 값을 최대화하기 위한 초기 배열의 reordering은?

우선 주어진 함수의 정의를 배열에 적용했을 때 규칙을 보기 더 쉽게 하기 위해서 &를 이용해 줄줄이 꿸 수 있는 형태로 바꿔보았다.

$$f(x, y)=(x|y)-y=x\&(\sim y)$$

따라서 마지막에 남는 값 하나는 (첫째 값 그대로)와 (나머지 각 값들 complement)를 전부 다 줄줄이 & 처리한 것이었다. 첫째 값으로 확인해봐야 하는 $n$가지의 경우의 수마다 빠르게 &연산을 해야 하므로 & 연산에 대한 prefix array와 suffix array를 모두 다 계산해두면 $O(n)$ 풀이가 된다.

42분에 AC

---

D: Aerodynamic

주어진 볼록다각형의 평행이동 중 원점이 포함된 평행이동들 전체의 합집합이 처음에 주어진 볼록다각형과 닮음인지를 판정해야 한다.

별다른 풀이가 안떠올랐고, 다른 사람들이 많이들 풀길래 그냥 찍어봤다.

1트: 홀짝 -> WA

2트: 점대칭 -> AC

 

증명은 editorial 참고.

---

총평

찍맞.

 

레이팅 변화 1797 + 38 = 1835

My Performance: ★★★☆☆

 

연습지