Codeforces Round #629 (Div. 3) 참가 후기

Round #627 이후 2주만에 Div. 3 라운드가 열렸다. 

 

그 사이에 Codeforces Global Round 7, Educational Codeforces Round 84 (Rated for Div. 2) 대회가 있었지만, 문제가 꽤 어려워 보여서 참가하지 않았다. 

 

5일 동안 종만북으로 갈고닦은 실력을 보여주지!

Dashboard - Codeforces Round #629 (Div. 3) - Codeforces

---

A. Divisibility Problem

$b - (a \bmod b)$를 출력하면 된다. 이때 나머지가 0이라면 0을 출력해야 한다.

 

설명 끝!

사실 이때까지만 해도 기세 좋았다. 다음 문제에서 아주 기초적인 실수를 하기 전까진..

 

B. K-th Beautiful String

 

길이 $n$인 문자열을 만들고자 한다. 문자열은 $(n - 2)$개의 $a$와 $2$개의 $b$로 이루어진다. 이러한 규칙을 적용하여 사전 순서로 문자열을 나열할 때, $k$번째 문자열을 구해야 한다.

 

문자열의 사전 순서를 결정해야 한다는 점에서 boj 1722번 문제와 유사하다. 우리는 $k$의 값에 따라 이 자리에 $a$가 와야 하는지, $b$가 와야 하는지를 결정해야 한다. 1722번 문제를 풀어 보았거나 적어도 고민해본 사람이라면 아주 쉽게 생각할 수 있는 내용이다.

 

그런데 왜 3번이나 Wrong Answer가 나오지? 내 코드 어딘가에 문제가 있는데, 어딘지를 모르겠다. 이걸로 정확히 27분을 날렸다.

 

하.. 결국 맞긴 했는데, 무슨 문제가 있었는지는 다음을 참고.

# 스포일러

$k$가 int 범위를 넘어갈 수 있다!

 

알고리즘에는 문제가 없다. 그런데 $n=100000$일 때 $k$의 최댓값은 $4,999,950,000‬$이다. 이걸 int에 저장하려고 하니까 오답이 나오지.. 

 

C. Ternary XOR

B번을 겨우 맞추고 나니 12시 38분이었다. 평소대로라면 지금쯤 이미 자고 있을 시간인데.. B번보다 C번 정답자가 더 많은 걸 보니 여기까진 풀어볼 만 하다. 조금만 더 하자.

 

(문제 설명은 생략합니다.)

 

편의를 위해 $a \geq b$ 라 가정하고, $x_{i}$가 될 수 있는 $(a_{i}, b_{i})$ 쌍을 생각해 보자.

 

• $x_{i} = 0$: $(1, 2), (2, 1), (0, 0)$
• $x_{i} = 1$: $(1, 0), (0, 1), (2, 2)$
• $x_{i} = 2$: $(1, 1), (0, 2), (2, 0)$

 

 

$0$을 만드는 최선의 방법은 $(0, 0)$이다. 마찬가지로 $1$을 만드는 방법 중 $(2, 2)$는 최악이므로 고려하지 않는다. 그럼 남은 방법으로 완전 탐색을 해야 하나? 최악의 경우 시간복잡도가 $O(3^{n})$이므로 여전히 문제를 풀 수 없다.

 

뭔가 최선의 방법이 있을 텐데.. 여기까지 생각한 순간 거의 1시가 다 되어 그만 자기로 했다. 다음날 아침에 문제를 풀긴 했지만, 확실히 풀어볼 만 했다는 점에서 많이 아쉽다.

 

# 풀이

$a$와 $b$를 만들다 보면 $a_{i} = b_{i}$이다가 어느 순간에 $a_{i} \neq b_{i}$가 될 것이다. 따라서 $a = b$인 경우와 $a > b$인 경우를 나눠 생각해 보자.

$a = b$

$a \geq b$를 만족하면서 1을 만드는 최선의 방법은 (1, 0)이다. (0, 1)은 제약 조건을 만족시키지 않는다. 한편 2를 만드는 최선의 방법은 (1, 1)이다. (0, 2)는 제약조건을 만족시키지 않으며, (2, 0)은 $max(a,b)$를 더 크게 만든다.

$a > b$, 즉 $a \neq b$

$a > b$를 만족하면서 1을 만드는 최선의 방법은 (0, 1)이다. (1, 0)은 $max(a,b)$를 더 크게 만든다. 2를 만드는 최선의 방법은 놀랍게도 (0, 2)이다. $a > b$를 만족하면서도 $max(a,b)$를 최대한 작게 한다.

 

각 경우에 따른 최선의 선택지를 알았으니, 이제 입력에 따라 $a$와 $b$를 만들어 보자.

---

총평

나름 도전의식을 불태우게 해 주는 라운드였는데.. B번 실수가 두고두고 아쉬움이 된다. 다음 대회에서는 1시간 안에 빠르게 3개를 풀어 보자.

 

 

다음 대회

Codeforces Round #630 (Div. 2) - 2020.03.31. 22:35 (UTC +9)

April Fools Day Contest 2020 - 2020.04.01. 23:35 (UTC +9)

 

 

코드포스가 구데기컵을 개최할 생각인가?