2025 KSA Automata Winter Contest 후기

2025.02.15 19:00 - 2025.02.16 00:00의 5시간에 걸쳐 KSA Automata Winter Contest가 진행되었다.

순위상이 무려 31등까지 있길래 열심히 5시간 문제를 풀면 무슨 상품이라도 받지 않을까 하는 마음에 5시간 한 번 불태워보자는 마음가짐으로 대회에 임했다.

대회 중 타임라인을 따라 구성하였다.

 

[00:00 - 00:01] A - 아름다운 수열 AC

거리가 소수인 두 다른 원소 사이의 차는 소수여야 한다.

거리와 원소 사이 차가 대응되기 때문에 그냥 1, 2, 3,... N을 출력하면 되는 게 아닌가? 싶어서 처음에는 문제를 잘못 읽은 건가 생각했다. 다시 읽어 봐도 맞는 것 같아서 그냥 그대로 구현해서 제출했다. 2분이 채 안 걸렸지만 10명 넘는 분들이 풀었길래 상품이 걸려 있으니 다들 열심히 하나 보구나 생각이 들었다.

 

대회 종료 후 난이도는 b2로 기여하였다. #constructive가 붙어서 그 이하의 난이도를 주고 싶기도 했지만 다소 부담스러웠다.

 

[00:01 - 00:15] B - 저녁 태권도 AC

처음 입력받은 값들을 이용해서 YES인지 NO인지 확인하고, YES인 경우 종이 카드를 사용할 수 있는 날에 그리디하게 종이 카드를 최대한으로 넣어주고, 모든 학생들이 다 종이 카드를 쓸 수 있도록 해주면 충분하다. 다만, 구현이 약간 시간이 걸렸다. 문제를 풀고 나서 스코어보드를 보니까 C 퍼솔이 B 퍼솔보다 먼저 나온 걸 보고 B 구현이 나만 오래 걸린 건 아니구나 하는 생각이 들었다.

 

그래도 아이디어 자체가 어렵거나 한 건 아니라서 대회 종료 후 s2를 기여했다.

 

[00:15 - 00:24] C - 미술 수업 AC

기울기가 1 또는 -1인 직선이 가장 먼저 보였다. x, y축에 평행한 직선이나 기울기가 1, -1인 직선들이 놓여 있는 문제들은 여러 번 본 적이 있어서 상당히 친숙했다. x+y랑 x-y값을 set에 넣어서 중복을 제거하고 투 포인터로 최종적인 답을 구했다.

 

구현이 어렵지 않아서 B보다 시간이 짧게 걸렸다. 그래도 투 포인터 자체가 실버에서 쓰이는 알고리즘은 아니라서 g5를 기여했다.

 

[00:24 - 00:44] D - KSA 문자열 2 AC

KSA 문자열 문제가 돌아왔다. 작년 Winter Contest에서도 KSA 문자열이라는 문제가 출제되었는데, 섭테 2만 맞는 코드만 몇 번 반복해서 제출하면서 맞왜틀을 당했던 기억이 난다. 그래서 문제를 풀면서 더욱 꼼꼼히 반례가 없는지 체크하고 신중하게 풀었던 것 같다.

문자열 내에서 K, S, A의 개수를 각각 세서 만들 수 있는 KSAAC 운영진이 좋아하는 문자열의 최대 길이를 쉽게 구할 수 있다. 그리고 여러 다양한 반례에 부딪히면서 어떻게 풀어야 할지 고민했다. 문자열의 길이가 정해지므로 맨 뒤에서부터 어떤 문자가 와야 하는지는 고정된다. 그리고 문자를 맨 앞으로만 옮길 수 있고 사이에 끼우거나 뒤로 이동하는 것은 안 되므로 뒤에서부터 순회하면서 KSAAC 운영진이 좋아하는 문자열과 일치하지 않는 문자가 있을 때마다 시행 횟수에 1을 더하는 방식으로 그리디하게 풀이할 수 있었다.

 

이 그리디 알고리즘 자체가 떠올리기 단순한 그리디는 아니라고 생각해서 g2를 기여했다.

 

[00:44 - 01:02] E - 수열의 점수 AC

문제를 읽자마자 피보나치의 느낌이 물씬 나는 점화식이 등장했다. 초항을 x, y로 두고 항 여러 개를 구하다 보니 x, y의 계수에 피보나치 수가 보였고, 그래서 x와 y의 비율이 황금비 (sqrt(5) + 1) / 2 근처로 수렴해야 한다는 사실까지 쉽게 찾을 수 있었다. 그래서 직관적으로 인접한 두 피보나치 수를 출력하는 것이 최선해가 아닐까 하는 추측을 하였다. 하지만 X, Y 값에 따라서 엣지 케이스가 존재하거나 인접한 두 피보나치 수보다 최선인 다른 쌍이 존재할 수도 있지 않나 해서 desmos를 활용해서 일차함수 몇 개를 그리고 그 사이에 끼어 있는 격자점을 관찰했다. 정확한 증명은 아니지만 인접한 피보나치 수가 항상 사이에 끼어있는 것을 보고 내 생각이 맞겠다 하는 확신을 가졌고, 곧바로 구현해서 제출하여 AC를 받았다.

 

증명의 난이도가 꽤 높다고 생각해서 g1을 기여했는데, 난이도 기여가 매겨진 걸 보니 g2로 책정되어 있었다. 다들 증명의 난이도보다는 직관을 통해서 AC를 받는 난이도를 위주로 기여하신 것 같았다.

 

여기까지가 전반전이었다. 내가 E를 풀었는데 F 퍼솔이 그제서야 나온 걸 보고 F부터는 만만치 않은 문제임을 직감했다.

그리고 뒤에는 정말로 어려운 문제들만 남아 있었다.

 

[01:02 - 01:50?] F - 멀티버스를 여행하는 한별이를 위한 안내서 고민

40분 정도 시간을 들여서 이 문제의 풀이를 고민했다. N, K가 소인수로 갖는 2의 개수와 5의 개수에 따라 케이스를 분류해 가면서 답을 어떻게 찾아야 할지 고민했는데, 큰 수확이 없었다. 그리고 대회 도중 F번 문제 인터랙터에 오류가 있다는 공지가 올라와서 그냥 F를 넘기기로 했다.

 

[01:50? - 02:40] I - KSA 수열과 쿼리 PA

스코어보드를 내리다가 I번 문제에서 39점을 받으신 분이 있는 걸 확인했다. 이제 더 이상의 AC가 힘들다면 섭테를 긁어야 되겠다 싶어서 문제를 읽었다. 섭테 1은 그냥 나이브하게 구현해도 받을 수 있고, 3점이라서 큰 메리트를 느끼지 못했다. 섭테 2는 K = 2인 경우로 1번 쿼리가 0을 1로 바꾸고 1을 0으로 바꾸는 쿼리에 불과하기 때문에 lazy propagation을 이용한 세그먼트 트리를 구성하면 어렵지 않게 풀리겠다는 생각이 들어 구현을 시작했다. 평소에 풀어본 lazy propagation 문제가 거의 없던 터라 구현에서 약간 애를 먹었지만, 그래도 50분 정도에 걸쳐 21점 섭테를 얻는 데에 성공했다.

 

[02:40 - 02:43] I - KSA 수열과 쿼리 PA

원래는 섭테 3까지 긁어서 점수를 챙기고 싶었지만 섭테 3조차 어떻게 풀어야 할지 감이 안 와서 그냥 섭테 1로 3점을 얼른 긁고 다른 문제로 넘어가기로 했다. naive하게 구현하면 되기 때문에 3분 만에 끝났다.

 

[02:43 - 03:39] H - 쿠키 공장 PA

섭테 3을 못 풀고 섭테 2만 맞은 사람들을 스코어보드에서 몇몇 봐서 섭테 2만 풀겠다는 생각으로 고민을 시작했다. 놀지 못하고 계속해서 쿠키를 만들어야 하는 시작점에서부터 만들어야 하는 쿠키 개수를 더해준 시간까지 일을 해야 하므로 시간 역순으로 (생산해야 하는 쿠키 수 누적 합) + (생산 시작 시각)을 모아놓고 이 중 최댓값이 답이 된다는 관찰을 했다.

이를 이용하니 각 생산 시작 시각을 세그먼트 트리의 노드로 잡고 max로 세그트리를 구성하여, 범위에 값을 더해주는 lazy propagation을 이용해서 또 다시 문제를 해결할 수 있음을 깨달았다. 앞선 I번에서 lazy propagation을 한 문제 풀어서인지 상대적으로 구현이 수월했다. 무려 54점이라는 부분점수를 받아 좋았다.

 

[03:39 - 04;17] F - 멀티버스를 여행하는 한별이를 위한 안내서 PA

H와 I는 이미 건드렸고, G와 J는 푼 사람이 나오지 않았기에 도전할 엄두가 나지 않아 다시 F로 돌아왔다. 다시 차근차근 생각해보니 a의 값이 0 이상 8 이하로 제한된다는 사실을 꺠달았고, 오일러 정리를 활용해서 이분 탐색으로 위수를 찾으면 된다는 관찰을 해냈다. 구현은 그렇게 어렵지 않아 제출하여 35점 서브태스크를 맞았다.

 

[04:17 - 04:38] F - 멀티버스를 여행하는 한별이를 위한 안내서 AC

가만 생각해보니 a값에 대해서도 이분 탐색을 할 수 있다는 걸 떠올렸다. 그래서 a값을 찾을 때에도 이분 탐색을 적용하고 보니 쿼리 횟수가 최대 11회였다. 그런데 가만 보니 a = 0인 경우를 제외하고는 K가 2 또는 5의 배수가 되어 굳이 4 * 10^7에서부터 찾을 필요가 없다는 사실을 깨달았다.

그래서 a = 0인지 체크한 이후에 a = 0이면 바로 이분탐색을 진행하고, a > 0이면 a값을 이분 탐색으로 찾은 후 K가 2의 배수인지 5의 배수인지 1회의 쿼리로 다시 체크하여 이분 탐색의 범위를 좁혀 효율을 높였다. 그러니 정확히 10회 안으로 모든 경우에 대해 답을 출력할 수 있었다.

 

대회 시작 1시간 이후로 처음 다시 받아보는 AC라 굉장히 뿌듯했다. 지금 돌이켜보면 이 문제를 PA로 마무리지었으면 내가 특별상을 탈 수도 있었지만, 높은 난도의 문제를 대회에서 푼 것 자체만으로 뿌듯하여 후회는 없다.

 

위수의 개념을 알아야 하는 부분이 있어 난이도가 꽤 높다고 판단했고, p1을 기여했다. 그런데 다른 분들은 나보다 더 어렵게 느꼈는지 d5를 책정받았다.

 

[04:38 - 04:45] 휴식

이제 정말 풀 만한 문제는 다 풀었다 싶어서 여기서 마무리지으려고 했다. 그런데 문득 H에서 섭테 1을 긁지 않은 게 떠올랐다. 스코어보드가 프리즈되어 있어 내 등수를 전혀 유추하기 어려워서 7점이라도 벌어야겠다는 생각에 H로 돌아갔다.

 

[04:45 - 04:53] H - 쿠키 공장 PA

이 역시 naive하게 구현하여 맞을 수 있는 섭테 1을 구현해서 7점을 추가로 확보하였다. 스코어보드가 공개된 이후 돌이켜보면 이 7점이 등수를 가르지는 않았다.

 

이렇게 해서 5시간에 걸친 긴 대회가 끝났고, 최종 순위는 13등이었다.

(이때 프리즈된 스코어보드를 생방송으로 하나씩 공개해 주셔서 보는 재미가 있었다.)

 

5시간 동안 쉬지 않고 대회 문제를 풀다 보니 정말 코드포스를 2-3번 연달아 친 듯한 기분이 들고 기진맥진해졌다.

그래도 상품을 받아 만족스럽다.

 

추가로, 대회가 끝나고 백준에 문제가 올라온 후 H 업솔빙을 했다.

solved.ac 디스코드에서 H번 섭테3에 대한 풀이를 물어보니 그냥 s가 수정되어도 원래의 s는 빼주고 새롭게 생긴 s에 더하면 된다고 하셔서 그냥 s를 미리 다 받아놓고 좌표 압축하여 세그트리에 넣으면 되겠구나 생각해서 구현을 했다. 그런데 예상치 못하게 현재 실제로 사용되지 않는 s값에 대해서도 최댓값 계산이 진행되고 있음을 깨닫고 한 단계 막혔다. 어떻게 구현해야 할지 고민하다가 그냥 사용되지 않는 s값에만 -10**9를 더해놓고 s값이 사용되는 상태로 전환되면 다시 10**9를 더하는 식으로 억지로 해결시켰다. 새로운 함수를 구현하기 귀찮아서 있는 함수를 더 사용해서 저 과정을 진행했더니, 실행 시간이 박살 났지만 업솔빙에 성공했다.

 

 

I도 업솔빙을 언젠가 해야 하지만 I 문제 난이도가 아직 내가 건드릴 수 있는 수준이 아닌 것 같아 먼 미래로 미루었다.

내 생애 가장 열심히 참여한 백준 대회인 것 같고 결과도 그만큼 잘 나와서 뿌듯했던 것 같다.