Day 315. 2023 국민대학교 & 중앙대학교 프로그래밍 경진대회 Open Contest 후기

8솔 폼미...

11등 폼미...

7번째 아레나 대회였던 2023 국민대학교 & 중앙대학교 프로그래밍 경진대회에서 처음으로 20등 안에 들었다. Unrated까지 감안해도 22등에다가 D번은 퍼솔까지 먹었다.

5번째 아레나 대회였던 SUAPC 2023 summer는 내가 출제진으로 들어가서 참여 자체가 봉쇄되었고, 처음 다섯 개의 아레나는 배치고사여서 레이팅에 가산점이 붙는다. 그런고로 6번째 아레나인 이 대회가 정확한 참가자의 실력을 표시할 수 있는 대회였는데, 예상도 하지 못했던 극상위권 퍼포먼스가 나와버렸다.

SSS 폼미...

타임라인은 다음과 같다.

00:01 A AC

진짜 간단한 브론즈 문제라 푸는 것이 그렇게 어렵지는 않았다. 실수오차가 발생할 것 같아서 포매팅을 조금 하느라 약간 시간을 소모했다.

 

00:03 B AC

스트릭 상태를 저장해주는 변수 하나만 계속 갱신해주면서 갱신할 때마다 최댓값을 비교하는 방법으로 쉽게 풀 수 있었던 문제였다.

 

00:19 D AC

구현량이 적지 않아서 다른 사람들이 전부 거른 티가 났다. 극초반 15분 정도는 A B를 모두 풀고 C D를 보다가 상당히 많은 구현량에 다들 넋이 나갔는지 반 동결 상태였다. 

C를 짜다가 예제마저도 틀려서 잠깐 덮어두고 D를 먼저 풀었다. 주 5회, 60시간 방송을 하지 않으면 가짜 버추얼 유튜버라고 한다. 문제에서 말하는 버추얼 유튜버의 정의는 에네 같은 느낌인 걸까?

구현이 조금 귀찮았지만 그래도 앞쪽에 배치된 문제인 만큼 정직하게 구현하면 답이 나오는 문제였다. 다른 사람들이 죄다 조금 더 구현이 쉬운 문제를 풀려고 뒤로 먼저 넘어갔는지 예상치 못한 First Solve를 여기서 따냈다.

 

00:32 C AC

E, F번이 생각보다 어려워 보여서 접어두었던 C번을 다시 잡았다. 어디서 자꾸 미스가 났는지 파악하는 데만 시간이 꽤 걸렸다. 방향성을 바꿔서 처음부터 다시 구현했고, 그렇게 어렵지 않게 AC를 따낼 수 있었다.

 

00:51 M AC

다른 문제들을 하나씩 다 읽어 봤다. 예제에서 뭔가 이러면 될 것 같다는 생각을 했고, 종이에 몇 줄 끼적끼적이다 보니 생각보다 어렵지 않게 답을 얻을 수 있었다. 길이 1인 케이스만 유의해서 예외처리를 해 주면 어렵지 않게 정답을 얻을 수 있는 문제였다.

각 비트마다 독립적으로 bitwise XOR가 작용하므로 단 하나의 비트에 대해서 길이가 2, 3, 4...인 케이스들을 손으로 써 가며 계산하다 보면 홀수 번째 혹은 짝수 번째 이항계수의 합 식이 나온다.

 

00:59 G AC

어쩌다 보니 5문제를 풀었고, 더 푸는 것도 불가능하지 않으리라는 판단 하에 남은 문제들을 읽어 보기 시작했다. N O 두 문제는 답이 없어서 일찌감치 걸렀고, J번은 SUAPC 2023 summer D번의 향기가 났다. K는 어떻게 해야 할지 감도 잘 안 잡히고, L은 어떻게 해야 할지 종이에 이리저리 식을 써 봐야 하는 과정이 수반될 것 같아 나머지 문제들을 읽기 시작했다.

G가 가장 만만해 보여서 그것부더 공략 시작했다. 책 읽듯이 왼쪽에서 오른쪽으로 읽고, 가장 오른쪽으로 갔다면 한 줄 아래로 눈을 낮춰 다시 왼쪽에서 오른쪽으로 읽으면 시선이 그리는 경로는 교차하지 않는다. 정렬 두 번만에 해결할 수 있는 문제였는데, 나는 조금 이상하게 정렬을 구현했다. 어쨌든 맞혔으면 된 거지 뭐.

 

02:04 H RTE

이상하게 N이 작은 것이 자꾸 마음이 걸려서 몇 개 손으로 계산을 해 봤다. N이 70000이더라도 최대 제곱근 수열의 길이가 5였다. 이러면 100% 맞겠지 하고 코드를 냈더니 반겨주는 게 RTE. 어디서 틀렸을까 디버깅용 예제를 만들어서 돌려 봤다.

 

02:05 H WA

이런 멍청이... 재귀함수로 풀려고 하나 만들어 놨었는데, 막상 잘 선언해놓고 return을 안 해서 에러가 났었다. 후다닥 고쳐서 다시 내 봤더니 WA. 이번엔 또 뭐가 문제일까...

 

02:13 H AC(+2)

\(\sqrt{A_i}=A_{i+1}\)인 케이스를 실수로 제곱수 순열로 판별해 버렸다. 방향성이 틀렸을지도 모른다는 생각을 해서 dp로 갈아엎으려다가 복귀했는데 쓸데없는 삽질이었다. 그것만 고쳤더니 AC.

 

02:33 I AC

N이 10이면 스도쿠 보드 가로세로 크기는 100이고, 따라서 들어갈 수 있는 숫자는 총 10000개이다. G 풀고 H 풀 때까지 생긴 1시간 텀이 사실은 I번에 대해서 고민한 결과였다.

가장 큰 돌파구가 되었던 힌트는 '소인수가 겹치면 안 된다면 그냥 상한에 가장 가까운 소수로 채우면 되는 것 아닌가?' 였다. 50만부터 100만까지의 소수는 총 36,960개. 이 소수들의 공통점은 자기 자신 빼고는 100만 이하의 다른 수와 공통인수를 가질 수 없다는 것이었다. 따라서 설령  9999개의 칸이 저 소수들과 겹치더라도 남는 소수가 상당히 많아서 스도쿠를 채우기에는 결코 어렵지 않다.

DB를 그대로 박아버린 탓에 260kB라는 무식한 코드 길이가 나왔는데, 다른 사람들은 어떻게 풀었을지 까봐야 될 것 같다. 일단 롱코더 1등상은 나에요...

 

여지껏 풀타임으로 참여할 수 있는 대회가 거의 없었다. 와쿠컵이나 브실컵같이 내 실력에 맞는 대회는 전부 내가 출제자로 참여해버려서 어쩔 수 없는 일이긴 하다. 전번의 대구소프트웨어고 프로그래밍 경진대회 이후로 오랜만에 대회 시간 꽉 채워서 고민할 수 있는 대회였던 것 같아서 기쁘고, 문제들 재밌었다.