Educational Codeforces Round 83 참가 후기

예전부터 이런 류의 대회 시스템에 참가하고 싶은 마음은 있었지만, 내 실력으로 과연 의미 있는 결과를 얻을 수 있을까? 라는 의심이 있었다. 그래도 어쨌든 해 보는 게 낫지 않겠나 싶어서 2월달부터 대회에 참가하고 있다.

 

그런데 평일 대회는 전부 밤 11시 35분 시작이다.. 늦어도 12시 반에 자는 내가 참가하기엔 너무 늦다. ㅠㅠ 그렇긴 하지만 마냥 미루기만 할 수도 없는 까닭에.. 다른 대회보다 상대적으로 쉬운 Educational Round에 참가해 보았다.

Dashboard - Educational Codeforces Round 83 (Rated for Div. 2) - Codeforces

---

A번 문제를 보았다.

볼록 정 N각형 내부에서 중심이 동일한 정 M각형을 만들 수 있는가?

 

???

이게 뭔 소리냐.. 라고 3초동안 생각했지만 이내 풀이를 고민하기 시작했다.

 

중심이 같다.. 즉 무게중심이 같다는 소리. 정N각형 내부에서 정M각형에 의해 나눠지는 바깥 면적이 모두 동일해야 한다는 뜻이다. 그렇다면 정M각형의 변 하나당 같은 수의 정N각형의 변이 매칭되어야 할 것이다. 이 조건을 만족시키려면.. M이 N의 배수여야 하지 않겠는가?

 

찾았다!

N이 M으로 나누어지면 문제에서 원하는 정다각형을 만들 수 있다.

빨리 제출하고 다음 문제로 넘어갔다.

---

B번 문제 제목이 Bogosort다. 이거 참 재미있는 정렬 방법인데.. 각설하고.

길이 n인 수열 a가 주어진다. 이 수열을 적당히 섞어서 모든 i < j에 대해 j - a[j] ≠ i - a[i]가 성립하도록 만들어 보자.

 

식을 변형하면 j - i ≠ a[j] - a[i]다. 이걸 만족하도록 섞어야 한다.. 브루트 포스 해야 하나? 그런데 n이 최대 100이라서 100!가지를 전부 탐색할 수 없다. 그렇다면 어찌해야 하는가?

 

한 10분 정도 고민하다가 이건 아닌 것 같아서 C번으로 넘어갔다. 결국 이건 끝까지 못 풀었다.

 

스포일러 주의!

# 풀이

j - i는 항상 양수다. 값은 매번 달라지겠지만 어쨌든 0보다는 크다는 뜻이다. 

그렇다면 a[j] - a[i]를 음수로 만들면 되지 않겠는가?

 

이 풀이는 한 상위 랭커의 풀이이다. 이런 간단한 방법이!

사실 나는 모든 a[j] - a[i] 쌍을 저장한 다음 최대 유량으로 풀어야 하나 하는 막연한 생각에 빠져 있었는데(그마저도 최대 유량은 구현해 본 적이 없다).. 어쩌면 시간의 압박 속에서도 이런 풀이를 생각하는 것이 진짜 실력이 아닐까?

---

C번을 읽는 시점에서 이미 시간은 12시 20분에 가까워지고 있었다. 그런데 의외로 피곤하지가 않았다. 오히려 대회 시작할 때보다 정신이 더 맑아진 것 같기도..?

 

실력에 상관없이 좋아하는 걸 하는 사람만이 느낄 수 있는 특권이 아닐지.

 

모든 원소가 0이고 길이가 n인 수열 v가 있다. i번 단계(i는 0부터 시작)마다 다음 중 하나만을 수행할 수 있다.
1. v의 임의의 원소를 골라서 k^i를 더한다.
2. 아무것도 하지 않고 다음 단계로 넘어간다.

이때 v를 주어진 수열 a와 같게 만들 수 있는지 판별하시오.

 

k의 거듭제곱의 합으로 수열 a를 만들어야 한다. 따라서 a의 모든 원소는 k의 거듭제곱의 합 꼴로 나타낼 수 있어야 한다. 또한 한 단계마다 하나의 수만을 증가시킬 수 있으므로, a의 모든 원소는 서로 다른 거듭제곱의 합으로 나타낼 수 있어야 한다.

 

a의 모든 원소 n에 대해, n을 k의 거듭제곱의 합으로 나타낼 수 있는지 판별해야 한다. 어떻게 할 수 있을까? n이 최대 10^16이기 때문에 브루트 포스는 불가능하다. 그렇다면 dp를 써야만 하겠다. 이전 결과를 저장해 놓으면 중복 체크를 최대한 줄일 수 있을 거다.

 

그런 다음에는 거듭제곱이 모두 다른지 검사한다. 같은 거듭제곱을 써야 한다면 a를 만들 수 없다.

(만들 수 없는 예: k = 2, a = [6, 10])

 

처음에는 파이썬의 dict를 사용해서 구현했으나 시간 초과가 나서 c++로 다시 구현하여 제출하였다. 그런데 이때 우리집 강아지도 안 할 실수를 저지른다. C번 코드를 B번 문제에 제출한 것이다!

 

ㅋㅋㅠㅠ

이건 뭐.. 덕분에 페널티 한 사발 했다.

---

D번을 읽긴 읽는데.. 더 버티기 힘들기도 하고 시간이 12시 50분 가까이 된 관계로 오늘은 여기까지 하기로 했다. 개인적으로 늦게 자는 게 몸에 맞지 않아서..

---

오늘 오후에 다시 들어가 보니, C번이 시간 초과가 났다?

???

아니.. 이건 또 무슨..

 

결국 내 최종 성적은 solve 1, wrong 2가 되었다. 

8667명 중 7122등

그리고 나는 Newbie가 되었다. 안 그래도 많이 떨궈놨는데..

와! 뉴비!

 

계속 공부하면 언젠간 나도 오렌지 달 수 있겠지?

 

다음 콘테스트

Codeforces Round #627 (Div. 3) - 3월 12일 23시 35분 시작(UTC +9)