UCPC(전국 대학생 프로그래밍 대회) 2021 예선 후기

사실 크게 나가야겠다는 생각을 하지 않고 있었는데,

에브리타임을 보다가 우연히 UCPC 모집글을 보게 되었고, 그냥 한번 나가볼까~ 해서 나갔다.

팀명은 마감하루전에타에서만나급조된팀 이였다ㅋㅋ

 

약 270개 정도의 팀이 참가했고, 10문제 중 5문제를 풀어서 72등이 되었다.

안타깝게도 본선에는 진출하기 힘들 것 같다.

그래도 정말 하루만에 급조된 팀 치고는 잘한 편인 것 같다ㅋㅋ

 

나는 B번, G번을 풀었는데, G번의 의도된 난이도가 플레티넘이라 정말 놀랐다.

B번은 단순 BFS문제였는데 최초로 푼 팀이 대회 시작 3분만에 풀어서 정말 놀랐다..

---

G번은 내가 느끼기에는 그냥 수학문제였는데, 여러 인스턴스에 대해서 노가다를 했다.

그렇게 규칙을 찾아서 규칙에 맞게 문제를 풀었더니 AC를 받았다.

 

박스가 K개 있고, 각 박스에는 숫자가 적힌 공이 N개 있다.

K개의 박스 중 임의로 2개의 박스를 고르고,

그 2개의 박스에서 각각 하나씩 공을 뽑았을 때, 공에 적힌 수를 더하여 나온 번호를 추첨번호로 한다.

 

이때, 그 어떤 임의의 두 박스를 골라도, 각 박스에서 선택한 공을 뽑아 나온 추첨번호가 항상 다르도록

즉, 언제나 각 숫자의 합이 중복되지 않도록 박스를 구성하는 문제였다.

(물론 박스1, 박스3의 조합에 유일한 3이 있고, 박스1, 박스2의 조합에 유일한3이 있더라도

서로다른 박스조합이기 때문에 이건 중복이 아니다.)

 

어떻게 접근을 해야할 지 몰라서 처음에는 그냥 무작정 써봤다.

예제 입력만 가지고는 인스턴스가 모자라서

일단 각 박스당 4개의 공이 있는 경우를 생각하고,

한 박스에는 임의로 1, 2, 3, 4 를 넣어서 생각했다.

다른 박스의 구성을 생각하기위해 다른 박스의 구성을 1, 2, 3, 4부터 하나씩 넣어봤다.

 

1,2,3,4 와 1,2,3,4의 조합은 중복이 매우 많이 나타났다.

그래서 숫자를 하나씩 뒤로 미뤄보다가, 숫자의 간격을 일정하게 넓히는 것을 생각했는데,

여기에서 첫번째 규칙을 찾았다.

 

우선 각 박스 조합에서 첫번째 숫자는 항상 1이어도 된다.

임의의 자연수 2개를 더해서 2가 되는 조합은 1+1 밖에 없어,

각 조합에 1이 하나씩만 들어있으면 2는 한 번 밖에 나올 수 없기 때문이다.

 

그 다음으로, 하나의 박스에 1,2,3,4가 있을 경우

다른 박스에는 공이 들어있는 개수보다 크거나 같은 간격으로 넓혀서 수를 적어야 한다.

 

1,2,3,4와 1,3,5,7 조합은 중복이 생기지만, (공이 4개씩 들어가는데 간격이 2이다.)

1,2,3,4와 1,5,9,13 은 중복이 없다. (공이 4개씩 들어가는데 간격이 4이다.)

 

처음에는 여기에서 착안해서 각 박스에 들어가는 공의 숫자 간격을 1씩 늘려나가도록 했다.

 

처음에 1,2,3,4로 했다면

그 다음에는 간격이 4인 1,5,9,13 (간격이 적어도 공의 개수만큼은 되어야 하므로)

그 다음에는 간격이 5인 1,6,11,16

...

 

이 이유는 수학적으로 증명하지 못했지만, 계속된 노가다로 찾은 규칙이다.

(좀 위험한 접근이긴 하지만..ㅋㅋㅋ)

 

이렇게만 해서 제출하니 바로 WA를 받았다.

그래서 다시 인스턴스를 여러게 실험하다 보니 한가지 문제점을 찾았다.

바로 간격이 3일때와 간격이 6일때 중간에 숫자가 겹치는 것이었다.

 

3, 6, 9, 12 를 더해주다가

6, 12, 18, 24.. 를 더해주니 중간중간 숫자가 겹치는 문제가 발생했다.

그렇다면 간단하다. 숫자 간격이 어떤 수의 배수가 되면 안된다.

정확히는, 각 숫자 간격은 서로소여야 한다.

 

이게 이 문제의 핵심 포인트였다.

박스당 최대 2000개의 공을 넣을 수 있고, 박스도 30개나 가능한 상황에서,

각 숫자 간격이 서로소가 되도록 맞추는 것은 쉽지 않다.

 

이럴 땐 그냥 어떤 상황에서도 두 수가 항상 서로소 관계인 소수를 쓰는 것이 맞겠다는 판단이 들었고,

상자가 최대 30개이니 그냥 인터넷에서 앞에서 30개의 소수를 긁어다가 리스트에 넣고,

하나씩 대입해서 쓰도록 했다.

(사실 에라토스테네스의 체를 쓰기가 귀찮았다..ㅋㅋㅋ)

 

그랬더니 WA가 나왔고, 상자가 4개인 케이스에서 실험했을 때,

간격이 2일 때와 간격이 3일 때 중간에 숫자가 겹치는 문제를 발견했다.

그래서 놓친 부분을 생각하다보니 아까 발견했던 규칙을 안써먹었다 ㅋㅋ

 

하나의 박스에 1,2,3,4가 있을 경우

다른 박스에는 공이 들어있는 개수보다 크거나 같은 간격으로 넓혀서 수를 적어야 한다.

 

저 인스턴스를 실험할 당시에는 규칙을 찾기 쉽게 1,2,3,4를 넣어놓고 비교를 했는데,

직감적으로 굳이 1,2,3,4가 아니어도 이 규칙은 성립하겠다는 생각이 들었다.

 

그래서 소수 중에 각 상자에 들어있는 공 개수보다 큰 소수간격으로 넓히도록 했다.

예를 들어 각 상자에 4개씩 공이 들어간다면

첫번째 상자는 5간격으로 1, 6, 11, 16

두번째 상자는 7간격으로 1, 8, 15, 22

 세번째 상자는 11간격으로 1, 12, 23, 34

이런 식으로 소수를 하나씩 늘려가도록 했다.

 

그리고 AC를 받을 수 있었다.

---

비록 처음 만난 사람들과 이룬 팀이었지만, 그래도 합을 잘 맞추어서 좋았다.

처음 UCPC팀을 모집해주셨던 팀장 같은 분이 워낙 문제를 잘 풀어주셔서 좋았다 ㅎㅎ

다음엔 기회가 된다면 아는 사람들과도 제대로 연습해서 나가보고 싶다 :)

(그 전에 군대부터..)