제5회 생각하는 프로그래밍 대회 참가 후기

지난 9월 18일에 충남대학교 알고리즘 동아리 ANA에서 주최하는 제5회 생각하는 프로그래밍 대회에 참가했습니다. 대회 마지막에 5솔브로 1등을 했고, PS를 시작한 계기가 되었던 제4회 생각하는 프로그래밍 대회때보다 훨씬 좋은 성적을 거뒀습니다. 이 글에서는 대회 시간인 3시간동안 시간 순서대로 어떤 일이 있었는지 이야기해보겠습니다.

대회 전

대회 중에 IDE는 사용이 가능하나, 인터넷 검색과 템플릿 사용이 불가능 하다는 규정을 듣고 자주 사용하지 않던 알고리즘 문제들을 다시 풀어보았습니다. 벨만-포드나 세그먼트 트리나 트라이를 보지 않고 짤 수 있을 정도로 구현을 연습했습니다. 막상 대회에는 출제되지 않았지만요... 또한 제가 평소에 약했던 분야인 시뮬레이션 빡구현 문제들을 위주로 풀어봤었습니다.

대회 시작 직전에 긴장을 엄청 많이 했습니다. 주변에서 제가 1등을 할 것이다라고 믿는 사람이 많았기 때문입니다. 하지만 CP와 PS는 다릅니다. 평소에 아무리 어려운 문제를 풀어본 적이 있던 사람이더라도 시간 제한이 있는 대회에서는 아무리 쉬운 문제여도 못 풀면 그걸로 끝입니다. 하지만 제 solved 레이팅은 세그먼트 트리 랭작때문에 너무 올라가있었고, 때문에 너무 많은 관심을 받았었습니다. 지금은 랭작이 별 의미가 없다는 것을 깨달았습니다.

13시 30분에 대회를 감독하는 줌 방에 입장했고, 줌으로 모니터와 키보드 마우스를 공유한 뒤 14시에 대회가 시작되었습니다.

A. 공사장 표지판

보자마자 별 찍기 문제임을 깨달았습니다. 만약 문제가 쉽게 나온다면 솔브 수가 같을 때 패널티가 더 적은 사람이 순위가 더 높습니다. 따라서 빠르게 풀어야 이득입니다. 하지만 그렇다고 틀리게 되면 패널티를 또 추가로 받으므로 정확하고 빠르게 맞추는 것이 중요합니다.
사각형으로 테두리를 둘러 싸고 가운데를 X자 모양으로 채워주면 되겠다 싶었는데, VScode가 말썽을 부려서 자동완성이 이상하게 동작했습니다. 아마도 프로젝트 파일을 연다음에 그 안에 있는 소스파일을 수정하는 것이 아니라 서로 다른 위치에 있는 소스파일들을 일일히 연결 프로그램-VSCode로 연 것이 문제인 것 같습니다. 그래서 아쉽게도 퍼솔은 놓쳤습니다.
00:08 AC

B. 참가자 명단

너무 문제를 급하게 읽어서 그런지 잘 이해가 안됐습니다. 일단 입력을 받는 코드를 작성하면서 우선순위 큐로 각 반마다 $M$개씩만 담아놓으면 되겠다 생각했습니다.

각각의 학급에 대해 학생의 이름을 길이가 짧은 것부터, 길이가 같다면 사전 순으로 출력한다.

B번 문제니까 단순 구현이겠거니 싶어서 문자열 정렬 기준은 String의 기본 정렬 기준과 동일하구나라고 생각했습니다. 하지만 일반적인 문자열 정렬 기준은 문자열의 길이와 상관 없이 알파벳 순입니다.
00:17 WA
처음에는 맞왜틀을 외쳤습니다. 스코어보드에서 제 친구도 동시에 틀린것을 확인하고, 분명 무슨 함정에 걸린 것이라 판단해서 조금 다시 읽어보다가 도저히 떠오르지 않았지만 바로 넘어갔습니다. 원래 저는 대회에서 쉬운 문제가 풀리지 않으면 좀처럼 뒷 문제로 넘어가지 않는 타입입니다. 이것 때문에 코드포스도 많이 망쳐봤습니다. 그런데 ainta님이 코드포스에서 B번이 안 풀리자 주저 없이 다음 문제로 넘어가는 모습을 보고 생각을 바꾸었습니다. 3분 정도만 더 고민해보고 C번으로 넘어갔습니다.

C. 도전 숫자왕

제한을 보기 전까지 2021 UCPC 예선 문제인 경품 추첨이 생각났습니다. 이거 업솔빙 안해봤는데, 그렇게 어려운 문제가 벌써 나오나 하고 생각했습니다. 그런데 $N \le 20$인 것을 확인하고 $2^{20}$ 브루트 포스로 하면 되겠다 싶었습니다. 입력 범위가 넓으니 바로 Map을 사용해줬습니다.
00:33 AC(First Solve)
이 때 스코어보드를 확인했을 때 4등이었습니다. 생각보다 빠르게 푼 사람이 많다는 것에 깜짝 놀랐습니다.

D. 뒤집기 게임

동전 뒤집기랑 매우 유사했습니다. 행동들을 시행하는 순서는 상관이 없으므로 열을 뒤집는 연산을 먼저 하고 그 다음에 행을 뒤집게 강제해줍니다. 열을 뒤집는 경우의 수는 $2^N$종류의 경우가 있습니다. $N \le 8$이므로 충분히 가능합니다.
00:53 AC(First Solve)
스코어보드를 보니 3등까지 올라왔습니다. 그런데 동시에 E번 First Solve가 뚫렸습니다. 어차피 다음으로 볼 문제이기도 했고 E번을 구경하러 갔습니다.

E. 리그 오브 레게노

계보 복원가 호석을 최근에 위상 정렬을 공부하면서 풀어봤었는데 이와 매우 유사한 문제라는것을 바로 알았습니다. 헌데 문자열을 처리하기가 귀찮아서 오래 걸릴 문제라는 것을 직감했습니다. 열심히 뇌절하면서 구현했습니다. 그런데 예제를 손으로 풀어보다가 B번에서 잘못 생각하던 것을 E번에서 깨달았습니다. 분명 같은 사전순이라 생각했는데 B번에서 문자열을 정렬하는 기준과 E번에서 정렬하는 기준이 달랐던 것입니다. 그래서 B번에서 했던 실수를 깨닫고 B번으로 돌아가서 고쳐주고 맞았습니다.
02:00 AC
E번이 좀처럼 잘 구현이 되지 않아서 다른 문제들도 구경해봤습니다. F는 딱봐도 백트래킹으로 안되고 어려워보였습니다. G번은 DP같긴 했는데 스코어보드를 보니 많이 틀려있는걸 봐서는 뭔가 함정이 있는 것 같았습니다. H는 중국인의 나머지 정리였습니다. 정수론을 등한시했던 저는 절대 맞출 수 없었죠 바로 걸렀습니다. 이 때 스코어보드에선 2등이었습니다 1등분은 G와 H를 열심히 박치기중이었죠. 그런데 D번을 푼 사람이 없다는 것에 놀랐습니다. 여기서 E를 맞춘다면 1등을 할 수 있을것만 같았습니다. 그러다가 일반적인 위상정렬과 BFS처럼 한 번 발견한 정점을 일단 모두 방문한 후에 새로 발견한 Indegree가 0인 정점을 q에 넣어야 된다는 것을 깨닫고 처음부터 다시 짜서 맞았습니다.
02:16 AC
스코어보드를 확인해보니 패널티는 많았지만 5솔을 한 사람이 없어서 1등이었습니다. 하지만 2등이 한개라도 더 맞춘다면 패널티차이로 인해 분명 밀릴것이 분명하기 때문에 G로 넘어갔습니다.

G. 백남이의 여행의 준비

앱처럼 DP점화식을 조금 다르게 세운다음에 쿼리를 통해서 하면 되겠다 싶었는데 좀처럼 구현이 잘 안됐습니다. 30분 남은 시점에서 스코어보드는 프리즈되었고, 2등분은 G와 H에 제출을 한 상태였습니다. 둘 중 하나라도 맞춘다면 바로 2등이 될 것이 분명했습니다. 결국 저는 G번을 풀지 못했고 그렇게 대회가 끝났습니다.

대회 후

대회 폐막식이 진행되는중에 F와 H를 제외하고는 모두 푼 사람이 있다는 소식을 들었습니다. 그렇다면 제발 2등분이 G를 못 풀었기를 바랐는데 스코어보드 오픈 결과 5솔은 저뿐이었고 1등을 지키는데 성공했습니다. 엄청 기뻤습니다. 다행히도 이번 대회에는 고수분들이 참전하지 않거나, 대회 운영진으로 참가해서 경쟁자가 줄었기 때문에 가능한 일인 것 같습니다.

내년 생각하는 프로그래밍 대회는 운영진으로 참가할 계획입니다. 코로나 상황이 더 나아져서 내년에는 원래 생프 대회처럼 오프라인으로 열 수 있었으면 좋겠습니다.