Codeforces Round #640 (Div. 4) 참가 후기

세상에.. Div. 4라니.

내가 생각하는 코드포스의 이미지는 가히 야생의 왕국(나는 풀 뜯어먹는 사슴..) 수준이라서, 초보들을 위한 대회가 이렇게 많이 논의되는 줄은 몰랐다. 이미 Div. 3이 존재하지 않는가?

 

Div. 4에 대한 고민을 담은 운영자의 글이 있으니, 읽어보길 권한다.

---

아무튼 그래서 나는 기쁜 마음으로 대회를 준비했다. 사실 준비라는 게 문제를 푼다던가 하는 게 아니고 컴퓨터 앞에 앉아서 시간을 기다리는 거다. ㅋㅋ

Div. 3에서 내가 보통 3문제를 푸니까, 여기서는 최소한 5문제 정도는 풀어야 하지 않을까 생각한다. 문제 수준이 대략 Div. 3의 A~D 정도 된다고 하면 그 정도 견적이 나온다.

 

이 대회도 어김없이 밤 11시 35분에 시작한다. 한 시간 안에 가능할지..?

Dashboard - Codeforces Round #640 (Div. 4) - Codeforces

---

A. Sum of Round Numbers

어떤 수 n을 $10^{i} (1<=i<=9)$의 배수의 합으로 나타내라.

이건 거의 브론즈 문제 아닌가? n의 자릿수를 추출할 줄 알면 쉽게 풀 수 있다.

빠르게 제출.

 

B. Same Parity Summands

어떤 수 $n$을 홀수만의 합 또는 짝수만의 합으로 나타내라. 그렇게 할 수 없는 경우 "NO"를 출력하라.

다음의 네 가지 경우를 생각할 수 있다.

1) $n$이 짝수, $k$가 짝수

$k-1$개의 $1$과 $n-k+1$로 표현하는 것이 가장 쉽다. 만약 $n-k+1$이 양수가 아니라면 "NO"를 출력해야 한다.

2) $n$이 짝수, $k$가 홀수

$k-1$개의 $2$와 $n-(k-1)*2$로 표현하는 것이 가장 쉽다. 만약 $n-(k-1)*2$가 양수가 아니라면 "NO"를 출력해야 한다.

3) $n$이 홀수, $k$가 짝수

항상 "NO"이다. 홀수를 짝수개 더하면 짝수, 짝수를 홀수개 더해도 짝수이기 때문이다.

4) $n$이 홀수, $k$가 홀수

1)과 같다.

 

코드포스 대회에 참가하면서 찾은 중요한 특성이 있다. "아무거나 출력하는" 문제를 풀 때는 가장 쉬운 답을 찾는 것이 좋다. 예제에서는 괜히 복잡한 답을 보여주는데, 그것은 수많은 정답 중 하나일 뿐이다.

 

이 문제도 마찬가지이다. 경우를 나눠서 생각해보면 어렵지 않게 풀 수 있다.

 

C. K-th Not Divisible by n

$n$으로 나누어 떨어지지 않는 $k$번째 정수를 출력하라.

$n$으로 나누어 떨어지지 않는 자연수는 $n$으로 나눈 나머지가 $1, 2, ... n-1$ 중 하나일 것이다.

즉 수를 $n-1$개씩 그룹으로 묶을 수 있다. 예를 들어 $n=4$일 때 이런 식이다.

Group 0: 1 2 3 (4)
Group 1: 5 6 7 (8)
Group 2: 9 10 11 (12)

자세히 보면, 그룹의 번호가 자연수를 $n$으로 나눈 몫임을 알 수 있다. 

 

그렇다면 $k$번째 수를 어떻게 구할 수 있을까? 위의 예시에서 $k=9$일 때(정답 $11$)를 생각해 보자.

우선 그룹의 번호를 구해 보자. 그룹에는 수가 $3$개씩 존재하므로 $k$를 $n-1$로 나눈 몫을 구하면 될까? 그렇지 않다. 위의 예시에서 $9$를 $4-1$로 나눈 값은 $3$인데, $9$번째 수는 $2$번째 그룹에 속한다. 그렇기 때문에 우리는 $k-1$을 $n-1$로 나눠야 한다.

 

그룹의 번호를 구했으니, 이제 실제 수를 구해 보자.

위의 예에서 그룹 $2$의 수를 분석해 보면 다음과 같다.

$9 = 2 * 4 + 1$
$10 = 2 * 4 + 2$
$11 = 2 * 4 + 3$

즉 k번째 수는 (그룹의 번호) * $n + offset$ 형태로 나타낼 수 있다. 이때 $offset$의 값이 $1, 2, ..., n-1$임에 주의해야 한다. $n-1$으로 나누는 나머지 연산으로는 $n-1$을 구할 수 없다. 따라서 우선 나머지 연산을 통해 $0, 1, 2, ..., n-2$를 구한 다음, 여기에 $1$을 더해야 올바른 $offset$ 값을 구할 수 있다.

 

정리하면 다음과 같다. / 기호는 정수 나눗셈을 의미한다.

group = (k - 1) / (n - 1)
offset = (k - 1) / (n - 1) + 1

answer = group * n + offset

 

 

발상은 쉬웠는데, offset을 구하는 과정에서 조금 오래 걸렸다. 그래도 아직까진 문제가 크게 어렵지 않다.

 

D. Alice, Bob and Candies

사탕 더미가 일렬로 놓여 있다. 각 더미에는 $a_{i}$개의 사탕이 있다. Alice와 Bob은 사탕을 먹는 놀이를 한다. Alice는 왼쪽에서부터, Bob은 오른쪽에서부터 사탕을 먹어나간다. 사탕은 Alice와 Bob이 번갈아가며 먹으며, Alice가 먼저 사탕을 먹는다.

이때 각 사람은 서로가 직전에 먹은 사탕의 수보다 더 많이 먹어야 한다. 모든 사탕 더미가 먹혀 없어지면 놀이가 끝난다.
Alice와 Bob이 먹은 사탕의 수를 구하시오.

지금까지의 문제에 비해 지문이 꽤 길어서 읽는데 조금 어려웠다. 특히 먹는 개수의 조건을 대충 읽어서..

 

문제를 올바르게 이해했다면 어렵지 않게 구현할 수 있다. 사탕 더미를 양 쪽에서 꺼낼 수 있어야 하므로 deque을 사용하자. 서로가 직전에 먹은 사탕의 수를 저장해 놓고, 그 수보다 더 많이 먹을 때까지 사탕을 꺼내면 된다.

 

Editorial엔 $O(n^{2})$짜리 해결책도 있던데.. 잘 모르겠다. 이게 가장 쉽고 빠른 정답이다.

 

E. Special Elements

Pay attention to the non-standard memory limit in this problem.

$1$부터 $n$까지의 자연수로 이루어진 수열이 있다. 수열에서 어떤 원소를 수열의 연속된 원소의 합으로 나타낼 수 있을 때, 그 원소를 특별하다고 한다. 주어진 수열에서 특별한 원소의 개수를 구하시오.

가장 단순한 해결책을 생각해 보자. 모든 연속된 구간의 합을 구하고, 수열에 그 수가 존재하는지 찾으면 된다. 이때 $O(n)$짜리 전처리를 하면 연속합을 $O(1)$에 구할 수 있다. 무작정 for문으로 구하면 전체 시간복잡도가 $O(n^{3})$이 된다. 이때 수열에 존재하는 수의 최댓값이 $n$이므로 $n$보다 큰 연속합은 무시해야 한다.

 

그런데 여기서 문제가 있다. 하나의 수가 여러 개의 합으로 표현될 때, 중복해서 세어진다는 것이다.

$6 = 1 + 1 + 4 = 1 + 2 + 3$

따라서 이미 카운트한 수를 저장할 필요가 있다. 

 

F. Binary String Reconstruction

(문제 설명 생략)

문자열을 적절히 만들라.. 이것도 가장 쉬운 해결책을 찾아야 한다.

 

그런데 잘 생각이 안 난다. 어떻게 해야 하지?

한 5분정도 고민하다가 빠르게 다음 문제로 넘어간다. 벌써 12시 반인데, 하나라도 더 풀어야지.

 

G. Special Permutation

$1$부터 $n$까지의 자연수로 이루어진 수열이 있다. 인접한 모든 두 수의 차이가 $2$ 이상 $4$ 이하가 되는 수열을 출력하라. 그러한 수열이 없으면 $-1$을 출력하라.

또 "아무거나 출력하는" 문제이다. 가장 쉬운 해결책을 찾으려 생각해 보는데.. 이것도 잘 안 된다.

 

그런데 $n$이 최대 $1000$으로 크지 않다. 그냥 다 해 보면 되지 않을까?

$i$번째 수를 정하는 재귀함수를 작성한다. 이전 수와의 차이가 $2$ 이상 $4$ 이하인 모든 수를 넣어 보고, 모든 수를 넣었다면 정답을 출력하면 된다.

 

예제를 넣어서 출력해 보니, 이런 결과가 나온다.

2 4 6 8 9 7 5 3 ...

뭔가 규칙이 있는 것 같기도 하고..

뭐 난 빨리 제출이나 하자. 108ms로 잘 돌아간다.

 

다시 F번

아.. 졸리다. 그래도 조금만 더 생각해 보자.

0000...0101...111 꼴로 만들어 볼까? 이건 조금만 해 봐도 반례가 수두룩한데..

 

오늘은 여기까지인 것 같다. 그만 자자.

# 풀이

 

101010...으로부터 시작한다.

문자열의 앞에 1을 붙여서, $n_{2}$개의 "11" 쌍을 만든다.

그 후, 첫 번째 0 뒤에 0을 붙여서 $n_{0}$개의 "00" 쌍을 만든다.

 

조금만 더 관찰했으면 풀었을지도? 아쉽네..

---

정리

확실히 문제가 쉬웠다. 7문제 중 무려 6문제나 풀었다.

 

심지어 레이팅도 무려 205점이나 폭등했다! 이게 과연 내 실력을 온전히 반영하는지는 모르겠지만 동기 부여는 확실히 된다.

 

언젠가 Div. 2에서 1등하는 날이 오길.