SUAPC 2026w 버추얼 후기

재원쿠선생님과 함께 쳤다. 

최근 들어서야 연속된 5시간 블록을 (거의)통째로 사용할 수 있게 되었다. 감사한 일이라고 생각한다.

본 대회였다면 5등 성적인데, 스코어보드도 없이 한 만큼 꽤 잘한 것 같다. 버스탄것도있긴하고 ..

 

내가 앞에서, 재원이형이 뒤에서부터 풀었다. 

 

A가 브론즈라 처음에 빨리 민 뒤 B를 읽었다. 순열에 먼가 연산을 잘 취하는? 코포틱하고 익숙한 포맷이라 그런지 만만하게 보여서 좀 생각해 봤다. 코포 B-C 정도일 줄 알고 쉽겠거니 했는데 풀이가 안 나오더라.. 일단 넘어가서 C, D, E, F까지 대강 훑었는데 바로 생각나는 게 없었다. C는 좀 귀찮아 보였고, D는 만만하게 생겼는데 아무 생각이 안 났다. E는 대충 봐서 제대로 생각도 안 했고, F는 쉬운 문제 or 개어려운문제일 것 같아서 좀 생각해봤지만 전혀 감을 못 잡았다. 그 사이 재원이형이 빠르게 M과 J를 풀어 왔다.

 

그나마 B가 할 만 해 보여서 계속 생각해 봤다. 일단 예제에 NO가 없고, 관상을 보아하니 안 되는 경우는 없어 보였다. 처음에는 단순히 첫 번째에서 N/2 이상을 왼쪽으로, N/2 이하는 오른쪽으로 잘 몰아두고 두 번째에서 다 짝 맞추는 식으로 접근했는데 먼가 명확한 풀이로 가는 느낌이 안 들었다. 일단 순열이니까 순열 사이클 분할을 해 봤고, 첫 번째 시도에서 모든 사이클의 크기가 2가 되도록 맞춰야 한다는 점을 생각하며 여러 시도를 해 봤다. 시도 끝에 swap 1번으로 크기 x인 사이클 하나를 크기가 각각 2, x-2인 두 사이클로 쪼갤 수 있다는 사실을 알 수 있었다. 출력할 때 swap하는 인덱스를 작은 것부터 출력해야 한다는 점을 놓쳐서 한 번 틀리고 맞았다. 맞았을 때까지도 쉬운 문제에 뇌절한 줄 알았는데, 끝나고 확인해 보니 이 풀이가 맞고 그냥 쉬운 문제가 아니었다

 

B 푸는 사이에 재원이형이 H까지 풀었다. 나는 이제 풀이 가닥이 나온 문제가 없어서 더 생각했어야 했고, 재원이형이 K 풀이가 대강 나왔다고 짜러 갔다. 나는 그나마 열심히 정리하면 될 것 같던 C를 잡았다. 결국 한 자리 수부터 시작해서 더 높은 자리 수들을 만들어 나가는 과정을 그대로 짜면 되는데, pq질을 하기에는 만들어지는 수들이 pq에 들어가는 순서가 크기 순이라는 보장이 없었다. 크기 순이 아니면 정확히 pq 크기가 맞을 때 자르면 안 되고 어느 정도 여유를 둬야 하는데, 이 개수 상한을 구하기 너무 귀찮았고 대강 해도 제한 안에 된다는 확신이 들었다. 여유를 과하게 둬서 TLE 2번을 맞긴 했지만 풀 수 있었다. 사실 아직 뚫은 건지 정확히 잘 한 건지는 모르겠다..

 

C를 푼 이후에 재원이형은 아직 K를 짜고 있었다. D는 감이 안 왔고, E를 제대로 안 읽었어서 찬찬히 다시 봤다. 예제에 일단 NO가 있으니 YES/NO 조건부터 생각해 봤고, NO인 예제를 두고 생각해 보니 가로와 세로의 홀짝성이 다르면 불가능하다는 관찰이 나왔다. 적당히 큰 정사각형에는 대각선으로 적당히 배치하며 조건에 맞게 만들 수 있고, 직사각형에서도 정사각형 영역을 자르고 남은 줄의 수가 짝수라면 한 줄에 몰아 넣으면 된다. N=3인 정사각형은 적절히 만들 수 있고, 변 중 하나의 길이가 2인 경우를 시도해 보니 불가능하다는 것을 알 수 있었다. 재원이형이 K를 열심히 짜더니 풀어냈고, 이후 바로 E를 풀었다. 

 

여기까지 했을 때 8솔에 본 대회 5등 성적이었고 시간은 1시간 반 정도 남았으며 충분히 풀었다는 생각이 들었다. 남은 문제 중에 만만해 보이는 게 없어 보이기도 했고..  재원이형은 G를 본다고 했고, 나는 L을 가지고 헛소리를 좀 하다 안 읽어본 I를 읽어 봤다. 

I는 일단 N=40이니 밋인더미들이라는 생각이 들었다. 더 생각해보니 $a_xa_y + b_xb_y$ 비슷한 모양의 식 중 최댓값을 구하는 꼴이 나왔고, 예전에 https://www.acmicpc.net/problem/24894 같은 문제에서 이런 꼴을 cht로 풀었던 게 생각났다. 이야기해보며 더 생각해 보니 저 문제까지 갈 필요도 없이 식 정리를 잘 하면 일차식 꼴이 나왔고, 밋인더미들으로 개수를 잘 관리하면서 cht로 최대를 찾으면 될 것 같다는 결론이 나왔다. 일단 재원이형이 더 잡아보기로 했고, 나는 G를 보러 갔다. 왼쪽에서 오른쪽 / 오른쪽에서 왼쪽으로 훑으며 각 점마다 담당하는 영역을 잘 관리하면 된다는 생각이 들었고, 셋질을 열심히 하면 될 것 같았다. 여기까지만 생각하고 일단 키보드를 잡았는데, 짤수록 시간 안에 절대안되겠다 싶었다. 20분 정도 남은 시점에 재원이형이 I 짤 수 있을 것 같다고 해서 나는 포기했고, 10분 가량 열심히 밋인더미들을 짜다 폭사하며 대회가 끝났다.

 

에디토리얼 까 보니 G는 별로 안 아쉬운데, I는 생각한 걸 그대로 짜면 되는 것 같아서 아쉬웠다. 지금 생각하면 G에 박은 시간을 D에 좀 투자했더라면 풀 수 있었을까? 싶기도 한데, 대회에서는 난이도를 모르고 푸니까 어쩔 수 없는 것 같다. 실제 대회였으면 슼보 보고 E를 먼저 잡아서 패널티가 줄었으니 등수가 좀 오르지 않았을까? 하는 희망회로도 열심히 돌리고.. 

 

아무튼 재밌었다. 5시간 대회가 생각보다 할 만 한 것 같다. 리저널 때는 두 번 다 개피곤했는데.. 아마 대회가 아침부터라 잠도 덜 깨고 컨디션 관리도 안 되어서 그렇지 않았을까? 진짜 열심히 하고 싶다