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

무려 3달만에 대회에 참여한다. 너무 오랜만이라서 조금 걱정도 되는데.. 잘 할 수 있겠지?

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

---

0:00 ~ 0:14

A번을 본다. A번은 어려워 보이지만 알고 보면 간단한 경우가 많기 때문에 너무 어렵게 생각하면 안 된다. 그런데..

 

A. 배열 $a$가 주어질 때, 차이가 1 이하인 임의의 두 수를 골라서 크지 않은 수 하나를 지운다. 이 연산을 0번 이상 반복하여 $a$의 원소를 하나만 남게 할 수 있을까?

 

간단한 문제다. 모든 인접한 두 수의 차이가 1 이하이면 "YES"를, 그렇지 않다면 "NO"를 출력하면 된다. A번다운 문제다.

 

그런데 왜 틀렸지?

??? 내가 아직 알지 못하는 크고 비밀한 것이 존재하는 건가? 아무리 봐도 아닌데?

 

망했다

여기서부터 말렸다. 말리면 실버 문제도 플래티넘처럼 느껴지기 마련인데, 어제의 내가 딱 그랬다. 3번 틀리고 나서는 이건 아닌 것 같아 넘기기로 했다. 

 

0:14 ~ 0:28

B, C라도 제대로 풀어야지.. 너무 급하게만 풀지 말자.

B. 여러 개의 사탕과 오렌지로 구성된 선물 $n$개가 존재한다. 세 연산(문제 참고) 중 하나를 0번 이상 적용하여 모든 선물의 사탕과 오렌지의 수를 같게 하고자 한다. 최소한 몇 번의 연산을 해야 하는가?

모든 연산이 사탕 또는 오렌지의 수를 줄이므로, 모든 선물의 사탕과 오렌지의 수를 최솟값으로 맞춰야 한다. 즉 모든 선물을 $(\min(a_{i}), \min(b_{j}))$로 만들어야 한다. 각 선물에 대해 $d_{a}~=~a_{i}-min(a_{i}),~d_{b}=b_{i}-min(b_{i})$를 계산하고, 더 큰(정확히는 작지 않은) 값의 합을 구하면 된다. 작지 않은 값을 구하는 이유는, 사탕과 오렌지의 수를 동시에 줄일 수 있는 만큼 최대한 줄이고 나서 남은 걸 마저 줄이는 방법이 최선이기 때문이다.

 

$a_{i}$와 $b_{i}$가 최대 $10^9$인데, 아마도 반복문으로 하나씩 줄이는 방법을 저격하려 한 듯하다. 다행히 이번에는 한 번에 Accept 받았다.

 

0:28 ~ 0:43

C. $n$명의 사람들의 몸무게가 주어진다. 사람들을 두 명씩 짝지어서 모든 짝의 몸무게의 합을 $s$로 같게 하려고 한다. 최대 몇 쌍을 만들 수 있겠는가?

$s$는 기껏해야 1250가지밖에 안 된다. $n$이 최대 50이므로 모든 $s$에 대해 짝지어 봐도 괜찮다.

 

우선, 가능한 모든 $s$의 값을 중복 없이 구한다. 중복이 있어도 되지만 굳이 중복 탐색할 이유가 없다. 그 후 모든 $s$에 대해 만들 수 있는 쌍의 개수의 최댓값을 구하면 된다. 사람을 짝짓는 게 조금 어려울 수도 있는데, 나는 ``std::map<int, int>``에 $w_{i}$의 개수를 저장해놓고, 모든 $w_{i}$에 대해 $s-w_{i}$가 존재한다면 두 사람을 짝짓는 방식으로 구현했다.

 

구현할 때 조금 막혔지만 한 번에 Accpet 받았다. 도대체 A는 왜 자꾸 틀렸던 거지?

 

0:43 ~ 1:16

D를 풀기에는 시간이 조금 부족해 보이지만 그래도 도전해 보기로 했다.

D. $0$과 $1$로만 이루어진 이진 문자열 $s$가 주어질 때, $s$를 최소의 부분 문자열(하단 참고)로 나누시오.

부분 문자열은 $010101...$ 또는 $101010...$과 같은 형식이어야 한다. 부분 문자열을 고를 때 반드시 연속된 문자열을 선택할 필요는 없다. 

 

왼쪽에서부터 그리디하게 전부 고르면 될 것 같다. 어떤 문자가 $0$이라면 그 문자로부터 시작하여 $010101$ 패턴을 가능한 한 길게 고르고, 문자가 $1$이라면 $101010$ 패턴을 가능한 한 길게 선택하자.

 

근데 틀렸네? 고민하면 될 것 같긴 한데.. 점점 머리가 느려지는 게 느껴져서 그만 풀기로 했다. 

 

# 틀린 이유

구현에 문제가 있었다. 나는 처음에 $0$과 $1$의 인덱스를 저장하는 큐를 두고 맨 앞 원소만을 보면서 부분 문자열을 골랐는데, 이러면 $0010$ 같은 예제에서 잘못된 답을 내놓는다. 큐 대신 ``std::deque``과 ``std::upper_bound``를 사용하여 인덱스를 찾으면 정답을 얻을 수 있다.

 

왜인지 모르겠으나 ``std::list``를 사용하면 시간 초과가 난다.

 

1:16 ~ 1:24

이미 시간은 밤 12시 51분이었다. 평소대로면 D를 풀다가 잤겠지만 오늘은 A를 맞히겠다는 집념으로 정신줄을 붙잡고 있었다.

 

그런데 아무리 해도 생각이 안 난다.. 결국 한번 더 틀리고 자기로 했다. 이대로 2솔브에 만족해야 하는가.

 

자려고 누운 자리에서

나는 그날 뭔가 아쉬운 게 있으면 잠을 잘 못 잔다. 딱 하룻밤이면 되는데 그 하루가 좀 힘들다. 어제는 생각을 안 하려 해도 안 할 수가 없었다.

 

인접한 수의 차이가 1 이하이면 확실히 YES이다. 1보다 커도 가능한가? 

 

이런 경우는 어떤가?

``5

1 3 5 4 2``

분명히 가능하다. 아.. 찾았다. 문제에는 분명히 차이가 1 이하인 임의의 수를 고를 수 있다고 했는데, 나는 인접한 수만을 골랐다. 문제 똑바로 안 읽냐?

 

아무튼 찾았다. 코드만 쓰면 되는데 이미 불 다 끄고 누운 상황에서 다시 컴퓨터를 켜기는 부담스럽고.. 급한대로 C++ 대신 파이썬으로 제출하기로 했다.

1시 9분 실화?

심지어 누워서 휴대폰으로 제출했다.. ㅋㅋㅋ 이런 일도 있구나.

---

결국 A를 맞췄지만 4페널티가 너무 컸다. 16672명 중 7119등으로 상위 42.7%다. 다행히 민트는 지켜냈다.

200점 깎일 각오 하고 있었는데 이 정도면 나름 선방? 

 

앞으로 열릴 Div. 2에도 슬슬 참여해 봐야겠다. 문제 풀 땐 항상 마음을 차분히 가라앉히자.