대회후기: Good Bye 2019

Goodbye 2019. What a year it has been.

올 한해가 지나면서 내 코딩인생 5년차, CP 도전 1년차를 마무리하게 되었다.

컴퓨터공학부의 입학과 함께 CP의 세계에 입문하게 된 2019년은 나에게 조금 더 특별한 해가 되었다.

 

Goodbye 2019, and hello 2020. What a year to come!

CP와 개발 공부를 계속해나가며 더욱 발전할 다음 1년을 기대해본다.

---

A: Card Game

A에서는 본 적 없었던 긴 description에 살짝 당황했지만, 내용이 매우 straightforward해서 약간 웃겼다. 뭔가 길게 썼지만 요지는 별로 없는 느낌? 두 배열이 들어올 때, 각 배열의 최댓값의 대소를 비교해주면 된다.

3분에 AC

---

B: Interesting Subarray

주어진 배열의 subarray중 최댓값과 최솟값의 차이가 그 배열의 크기보다 같거나 큰 배열이 존재하는지 판별하고, 존재한다면 찾아 출력하는 문제이다. Sliding window 알고리즘과 비슷한 느낌으로 subarray의 오른쪽 끝을 이동시키면서, 새로 발견한 값을 기존의 maximum혹은 minimum값과 교체할 시 배열 크기의 감소량을 최대 최소 차이의 감소량보다 키울 수 있는지 확인하였다. "이게 돼?" 느낌으로 해봤는데 되더라.

2 WA 후 27분에 AC

 

알고보니 인접한 값 사이의 차 중에서 2 이상이 존재하는지만 살펴보면 되는 문제였다... 풀이를 알고 보면 엄청 쉬운 문제.

---

C: Make Good

A set of numbers가 주어졌을 때, 최대 3개의 정수를 추가해 다음 조건이 만족되도록 만들어야 한다: (모든 숫자의 합) == 2(모든 숫자의 XOR값). 출력할 수 있는 수의 범위가 $10^{18}$까지 가능하길래 충분히 큰 수를 이용해 XOR값을 싹 다 지워버리고 원하는대로 조율해나가는 풀이를 떠올렸다. MSB를 제외한 모든 비트의 XOR 결과를 0으로 만들기 위해 $2^{54}+(적당한 수)$를 일단 추가하였다. 이제 XOR값의 두배는 $2^{55}$가 되었으니, 이 값을 변화시키지 않으면서 합만 조절하면 된다. 처음 한참 동안은 XOR값이 1이 되기 위해서는 1이 단 하나 존재해야 한다고 착각하고 있었으나, 반복된 WA의 이유를 분석해보던 중 XOR값은 1의 개수의 홀짝성에 의존함을 알아차리게 되었다. 모자란 합을 동일한 두 숫자로 나눠서 더해준다면 각 자릿수에서 1의 개수가 0 또는 2개 추가되기 때문에 XOR값은 유지된다. 모자란 합이 홀수인 경우는 어떡하지?라고 생각했지만 바로 그런 경우는 없다는 것이 보였다.

3 WA 후 1시간 30분에 AC

 

대회 종료 후 Editorial을 보니 주어진 숫자들의 합 $S$와 XOR값 $X$에 대해 두 숫자 $X$와 $S+X$를 추가해주면 해결되는 것이었다. 근데 이걸 어떻게 떠올린담;;

---

D: Strange Device

코포에서는 거의 처음 보는 interactive problem이다. $n$개의 숫자가 있는데, 그 값들은 직접적으로 알 수는 없지만 $k$개의 location에 대한 query를 넣을 수가 있다. 대답으로는 $k$개의 값들을 오름차순 정렬했을 때 $m$번째 위치에 있는 숫자의 처음 배열에서의 index와 value를 알려준다. $n$과 $k$는 알려진 값이지만, $m$은 정해져는 있지만 알려져 있지 않은 값이다. 이때 최대 $n$개의 query를 이용해 $m$값을 찾아야 한다.

Query를 이용해 최대한 많은 위치의 값들을 찾아낸 후, 그 값들을 이용한 어떤 query를 통해서 $m$값을 찾을 수 있지 않을까라는 생각에 여러 example들을 이용해 일반화된 알고리즘을 구상해보고자 하였으나 대회 종료시간까지 풀지 못하였다. 문제 해결의 실마리는 $k+1$개의 값들만 선택해 그 안에서 $k$개씩 고른 query를 전부 다 시도해보는 것이었다. 대답으로 돌아온 값들은 경우에 따라 $k+1$개 수 중 $m$번째 값과 $m+1$번째 값으로 두가지 경우인데, 둘 중 작은 값의 occurence를 세보면 그 개수가 $k+1-m$이고 큰 값을 세보면 $m$이다. 이로써 정답이 도출된다.

---

총평

2019년의 마무리는 레이팅 떡락과 함께~

할말은 없다. 문제들이 정답을 알면 쉽지만 모르면 풀이가 안보이는 종류였다.

지난 대회의 결과는 잊고 2020년 다가올 대회들을 기대해보자.

 

레이팅 변화 1733 - 38 = 1695

My Performance: ★★★☆☆