2025 고려대학교 프로그래밍 경시대회(KCPC) 후기 - 1

예비소집

 예비소집은 현장 참가는 아니고 Open Contest를 통해 참가하게 되었습니다. 예비소집 관련 특별상을 못 받는 건 아쉽지만, 대회 환경에 대해서는 MatKor컵을 참여하면서 어느 정도 파악이 되었기 때문에 크게 문제되는 일은 없을 거라고 생각했습니다. 문제는 어쩌다보니 폰코딩으로 풀게 되었습니다.

 

가장 먼저 A번을 봤는데 예제를 보니 $X_{2N + 1} = (10^N + 1)^2$일 거라고 쉽게 유추해볼 수 있었습니다. 조금 생각해보면 $X_{2N+1}$은 제곱수여야 하고 $(10^N)^2$ 이상이어야 합니다. 그런데 $10^N$은 분명 팰린드롬이 아닙니다. 하지만 $10^N+1$, $(10^N + 1)^2$과 $(10^N + 1)^4$은 모두 팰린드롬이기 때문에 추측이 맞다는 것을 알 수 있습니다. $X_1 = 1$만 예외처리하고 쉽게 AC를 받을 수 있었습니다.

 

[00:04:38] A번 AC

 

놀랍게도 오픈콘 기준으로 퍼솔이었습니다.

 

그 다음에 B를 봤는데, 매끈매끈하고 푱푱한 바닥에 놓인 세에그트리가 저를 기다리고 있었습니다. 잘은 모르겠지만 케이스워크 또는 계산기하 느낌이 들었습니다. 폰코딩+암산으로 풀기에는 무리가 있을 것 같아 일단 점프했습니다.

 

이어서 C를 봤습니다. 조금 고민해보니 직사각형 내부의 숫자들이 모두 다르려면 직사각형의 넓이가 10을 넘어갈 수는 없다는 것을 알았습니다. 넓이가 10 이하인 직사각형의 수는 27가지입니다. 그러면 왼쪽 위를 고정하고 가능한 직사각형 형태 27가지를 점검하면 될 것 같은데... 약 2억번 정도의 연산이 필요해서 잘못하면 TLE가 날 것 같다는 생각이 들었습니다. 아마 그냥 제출했어도 적당히 돌았을 것 같은데, 폰코딩으로 5중 for문 + 슬라이딩 윈도우를 짠다는 선택을 해버렸고... 어떻게 AC를 받긴 했습니다.

 

[00:40:40] C번 AC

 

D는 N, M 범위가 작으면 어쩌지 싶었는데 충분히 크게 나왔습니다. 그냥 $X_i \times 1$짜리 2차원 배열에 전부 0 채우면 된다고 생각하고 제출했습니다만...

 

[00:44:58] D번 WA

 

틀릴 포인트가 안 보인다 싶었는데, 지문을 살펴보다가 a, b가 1 이상이라는 조건을 뒤늦게 발견했습니다. a, b를 0에서 10으로 바꿔서 다시 제출하고 AC를 받았습니다.

 

[00:47:26] D번 AC

 

E는 동일한 모양의 위치만 다른 두 직사각형 영역을 잡으면, 상수값 만큼의 차이가 난다는 것을 관찰을 통해 알 수 있습니다. 따라서 모양만 같으면 직사각형 영역들은 전부 조건을 만족하거나 혹은 전부 만족하지 않는다는 것을 알 수 있습니다. 각 테스트 케이스에 대해 27가지 경우를 체크하는 코드를 제출했습니다. 그런데 왜인지 WA를 받았습니다.

 

[00:54:47] E번 WA

 

N, M이 크기가 꽤 크다는 사실을 떠올렸고, 변수들을 다 long long으로 바꿨습니다. AC가 나오리라 믿고 제출을 헸으나...

 

[01:00:28] E번 TLE

 

하필 TLE가 나왔습니다. 혹시 직접해보지 않아도 a, b값으로 바로 유추할 수 있나 싶었는데 그건 무리일 것 같았습니다. 결국 궁여지책으로 비트마스킹을 사용하기로 했습니다. 첫번째 행의 값만 비트마스킹으로 표현하면 다른 행의 비트마스킹들도 평행이동으로 표현할 수 있으니 조금 더 빠를 것이라고 믿었습니다. 설렁설렁할 줄 알고 폰코딩으로 했는데 이런 짓까지 하게 될 줄은 몰랐습니다...

 

[01:09:42] E번 AC

 

맞기는 했습니다만 988ms라는 매우 빠듯한 시간이 나온 걸 보게 되었고, 코드가 심히 비효율적이라는 것을 알게 되었습니다. 하지만 대회 중이니 쿨하게 넘어갑시다.

+ 기분 좋게 퍼솔을 하나 더 챙기게 되었습니다.

 

이후 F를 고민해보았는데, 해싱+투포인터로 풀릴 것 같다는 결론이 나왔습니다. 우선 정방향으로 해싱 + 뒤집어서 읽은 내용으로 해싱을 한 다음, 중앙을 고정한 상태에서 세로는 줄이고 가로는 늘리는 식으로 투포인터를 하면 $O(N^2 M)$에 풀릴 것 같았습니다. 다만 남은 시간을 고려할 때 폰코딩으로는 많이 무리라는 생각이 들었습니다.

 

아까 미뤄두었던 B를 보니 많은 사람들이 푼 상태였습니다. 많은 사람들이 풀었으니 의외로 단순할 수도 있겠다는 생각을 갖고 문제를 봤는데...

풀이는 모르겠지만 예제가 너무 $min(a, b)^2$과 $|a - b|$이었습니다. 시간도 별로 없으니 바로 코드 짜서 제출을 했습니다.

 

[01:48:50] B번 RE

 

...너무 급했는지 입력을 잘못 받았습니다. 그냥 정수 두 개 받는 건데... 고치고 다시 냈는데 이번에는 WA를 받았습니다.

 

[01:51:16] B번 WA

 

생각해보니 기약분수로 출력하랬으니 최대공약수로 나눠줘야 할 듯 합니다.

 

[01:57:07] B번 AC

 

다행히 AC를 받게 되었습니다. 3분 안에 F를 풀 가능성은 정말 없으니 여기서 마무리 하였습니다.

 

 

 

예비소집 결과

 이상한 실수도 많이 했지만 그런 것치고는 괜찮게 본 것 같습니다. 퍼솔도 두 개나 챙기고 풀어야 하는 문제는 다 푼 것 같았습니다.

본대회까지 끝나고 예비소집 스코어보드도 프리즈가 풀렸는데 2등을 하였습니다.

그냥 노트북으로 참가했으면 오랜만에 오픈콘 1등 가능하지 않았을까 싶긴 한데... 중요한 건 본대회니까요. 일단 배경지식을 강하게 요구하는 문제들은 아니어서 이번에는 느낌이 좀 괜찮았습니다.