SUAPC 2023 Summer Open Contest (Arena #5)

블로그에 처음 쓰는 아레나 후기 글이다. 아레나 #1은 계절학교와 병행해서 + C를 그냥 못 풀어서 등수를 박았고, 아레나 #2는 할 만큼 했으나 페널티로 인해 낮은 퍼포를 받았다. 두 대회 모두 딱히 복기할 거리도 없었다.

아레나 #3인 MatKor Cup은 깡수학 대회라길래 걸렀고, 아레나 #4 KSA 대회는 검수진이었다. 이러한 상황에서 아레나 #5인 SUAPC는 잘 칠 필요가 있었기 때문에 조금 집중해서 대회를 쳤다. SUAPC는 지난 2번의 대회에 출제진으로 참여한 적도 있었던 만큼, 기대를 안고 대회를 쳤다.

 

 

~0:12
대회를 켰는데, 일단 문제 수가 많았다. 내가 알기로 SUAPC는 13문제 체제로 유지되었던 것 같은데, 14문제가 나를 반기고 있었다. 같은 상황을 겪은 PPC와 대충 비슷한 이유로 문제 수가 늘어났을 거라는 유추를 할 수 있었다. 아무튼 문제를 다 키고 슥 훑어봤는데, 주는 문제가 없어서 좀 당황했다. 대충 그림이 있는 D를 보고 있었는데, 스코어보드에서 L 솔브가 나와 바로 보고 풀었다. \(K\)가 작아서 쉬운 풀이도 가능한데, 나는 별 생각을 하지 않고 그냥 \(O(NlogN)\)풀이를 짜서 냈다. 대신 수식 미스로 페널티를 1회 쌓아야 했다.

 

~0:19

이후 G가 풀려서 읽으러 갔다. 출제자가 원하는 풀이가 문제에 보여서 그냥 생각하지 않고 짜서 맞았다.

 

~0:27

다음으로 풀려 있는 문제인 I를 봤다. 문제에 포함 배제와 \(O(1)\) nCr을 짜라고 적혀 있길래 열심히 짰다.

 

~0:36

후기가 아니라 템플릿을 쓰는 것 같다. 여튼 K가 풀려 있었고, 공책에서 열심히 식 정리를 한 후 옮겨서 맞았다.

 

~1:16

K까지 풀고 나니 스코어보드에서 더 풀린 문제가 없어서 처음에 보던 D로 다시 갔다. D는 얼마 전 검수한 문제와 비슷한 느낌의 DP였다. 식 정리가 조금 귀찮긴 한데 결국 풀어야 하는 문제라 비교적 일찍 잡았다. 30분 정도를 쓴 후 예제가 나와서 냈지만 틀렸다. 다행히 비교적 빨리 찾을 수 있는 오류였고, 고쳐서 냈더니 맞았다. 퍼솔이라 기분이 좋았다.

 

~1:35

D를 풀고 오니 밀린 문제가 꽤 있었다. 일단 제일 많이 풀린 H를 봤다. 설명이 좀 복잡하긴 했는데 결국 그냥 구현 문제였다. 열심히 짰는데, .00을 .0으로 출력해 한 번 틀렸다. 이 날 잠을 제대로 자지 못해 전체적으로 식 정리를 절었는데, 아무튼 20분을 써서 H를 무사히 맞을 수 있었다.

 

~1:51

F가 꽤 풀렸길래 F를 봤다. 색을 칠하는 것은 KMP를 돌리는 과정에서 imos로 체크를 해주면 되며, 게임 형태가 NIM 게임과는 좀 다르지만 조금 써보니 그런디 수도 그냥 \(x\)라는 것을 알 수 있었다. 그대로 짜서 맞았다.

 

~2:13

다음으로 잡은 문제는 J이다. \(N\) 미만은 쉬웠다. 22222..3을 이용하는 문제를 코포에서 본 적이 있어서 비교적 빨리 떠올릴 수 있었다. \(N\)은 조금 어려웠는데, 직관으로 짤 수도 있었지만 불안해서 간단한 증명을 한 후 코딩에 들어갔다. 생각한 대로 짰고, sort에 cmp 함수를 넣지 않아서 한 번 틀렸다. 이 정도는 예제에서 막아주면 좋았을 것 같다.

 

~2:37

J를 푼 후에는 사람들이 많이 푼 A를 보고 있었는데, 잘 모르겠어서 브루트포스를 짜기로 했다. 그렇게 A 브루트포스를 짜는 동안 E가 풀렸길래 슬쩍 읽으러 갔다. E는 이상하게 생긴 그래프가 있어서 선인장 어쩌고인 줄 알고 넘겼었는데, 문제를 읽어 보니 그냥 이분 그래프에서 Maximum Independent Set을 찾으라고 시키고 있었다. 성게 중심을 뽑아내는 것도 딱히 어렵지 않아서 바로 긁어서 맞았다.

 

~3:39

다행히도 A의 브루트포스 풀이에서 어렵지 않은 규칙을 찾을 수 있었다. 바로 코딩해서 냈는데 틀린 후, 20분 정도를 써서 지문에서 1이 연속하지 않아야 한다는 내용을 발견하였다. 조금 복잡한 다른 규칙을 찾아서 맞았다.

 

~5:00

남은 문제로는 B, C, M, N이 있었다. 풀린 수가 대충 비슷해서 모든 문제를 읽어보았다.

B. 씹덕 지식이거나, 지옥의 식 정리를 통해 규칙을 때려맞추는 문제 같았다.

C. 행렬 거듭제곱인데 state를 열심히 줄이라는 문제 같았다.

M. 모르겠었다.

N. 스플레이로는 확실히 되고, 제한을 보면 루트질인 것 같았지만 짜기 싫었다.

 

결국 B를 잡았고, 1시간동안 식 정리를 하지 못한 채 멸망했다. 다행히 10솔 초과가 많지 않아 in 10 턱걸이를 할 수 있었다.

 

셋에 대해 느낀 점을 간단히 말해보자면, 9솔까지와 10솔부터, 특히 11솔부터는 체감 난이도가 상당히 컸다. 위 멘트들에서도 볼 수 있듯이 충분한 사전 지식이 있다는 가정 하에 9솔까지는 문제를 해결하기 위해 별다른 노력을 들이지 않아도 되었다. 물론 어려운 일이지만, 쉬운 문제에서도 충분히 배울 점이 있을 수 있는데 이러한 부분이 약간 모자른 것 같았다. 콜포테를 받지 않은 영향이 있을 수도 있지만, 자세한 부분은 잘 모르겠다.

 

셋 외적으로는, 본 대회 스코어보드를 통해 서강대/연세대 팀이 상당히 강하다는 것을 알 수 있었다. 서강대 팀이 12솔, 연세대 팀이 11솔인데 이러한 불 셋에서 11솔 이상을 찍은게 조금 놀라웠다. 특히, M은 감도 잡지 못했는데 본 대회에서 2솔이나 나온 것을 보고 좀 당황했다. 아마 이 대회를 ICPC 팀으로 쳤다면 수학 2문제 (B, C)를 남은 두 팀원이 각각 하나씩 풀어준 후, 내가 M이나 N을 풀어야 13솔인데.. 좀 쉽지 않은 것 같다. M같은 문제를 푸는게 팀 내에서의 역할인 만큼 공부를 더 해야겠다.