SUAPC 2022 Summer 참가 후기

 

2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2022 Summer)에 "우승하러 왔습니다"라는 팀명으로 참가하였다. 조금 늦었지만, 매 대회마다 후기를 작성해온 만큼 이번에도 간단하게 후기를 작성해보려고 한다. 

 

팀원은 djs100201과 lem0nad3으로, 올해 ICPC 멤버로 참가한 첫 대회이며, 성적은 1위(Kakao Tech상)를 차지하였다. 

 

스코어보드 상에선 나오지 않았지만, 참가자 명이 suapc 전 우승자 (나), suapc 전전 우승자 (djs100201), suapc 현 우승자 (lem0nad3)으로, 이번 대회까지 우승해서 최근 세 대회 우승자가 모두 있는 팀이 되자는 의도였는데, 현실이 되었다. 

 

 

지금까지 총 5번의 SUAPC를 참가했는데, 5위 → 3위 → 2위 → 1위 → 1위로, 꽤 이상적인 결과를 거두었다.

아마 이번 대회가 마지막일 가능성이 높지 않을까 생각하는데, 좋은 결과를 얻어서 다행인 것 같다. 

 

2022 SUAPC Winter 후기 : https://rebro.kr/196

2021 SUAPC Summer 후기 : https://rebro.kr/168

2021 SUAPC Winter 후기 : https://rebro.kr/114

2020 SUAPC Summer Div.1 후기 : https://rebro.kr/56

 

 

  1. 대회 요약

이번 대회는 총 52팀이 참가했으며, 역대 suapc 중에서 가장 스코어보드가 예쁘게 나오지 않았나 싶다.

사실 수상권이 모두 7솔이었던 지난 대회가 너무 밸런스가 극악이었긴 하지만, 항상 참가자들의 수준에 비해 고난도 문제가 많이 나오는 것 같아서 개인적으로 아쉬운 부분이 있었는데, 이번에는 프리즈 이후에도 문제가 많이 풀리고, 페널티 싸움이 된 것도 아니고, 안 풀린 문제도 1개밖에 없는 걸 보면 꽤 밸런스 있게 문제가 출제된 것 같다. 

물론, 우리 팀이 잘 봐서 "내가 잘하면 좋은 셋" 이 되어버린지는 몰라도... 역대 대회 중 가장 끝까지 치열했던 대회임은 확실하다. 

 

22.09.20 13:30 기준 난이도

 

티어는 다음과 같다. 상위권의 실력이 꽤 올라간 건지, 이전 대회들에서는 웬만하면 풀리지 않던 다이아 문제가 이번에는 D번을 제외하고는 모두 풀렸다. 

 

또, 이번 대회는 저번 대회와 달리 버스 승객으로 탑승했는데, djs100201의 승차감이 매우 좋았다. 개인적으로 PS를 소홀히 한지가 1년이 넘어서 실력이 많이 떨어졌는데, 대신 옆에서 서포트하는 역할이 꽤 효과적이었던 것 같다.

문제 풀이의 아이디어는 확실히 djs100201가 정말 잘 떠올리고, 대회 중반부터는 옆에서 풀이 검증이나 코드 구현 등을 도와주는 방식으로 진행했는데, 다행히 결과가 좋게 나왔다. 

그리고 lem0nad3은 우리 팀의 기하 문제를 맡고 있는데, 이번 대회에서는 기하 문제가 나오지 않았고, 또 고급 자료구조 문제도 꽤 풀어온 걸로 알고 있는데, 이 또한 문제로 나오진 않아서 아쉬움이 있었다. 아마 이런 유형이 꽤 나오는 icpc에서는 많은 역할을 할 수 있지 않을까 싶다.  

대신 진척이 없던 E번 문제의 해결 실마리를 마지막에 찾아서 1등 할 수 있었던 결정적인 원인을 제공했다. 

 

쓰다 보니 버스만 탄 것 같은 기분이 들긴 하는데.... 버스를 잘 타는 것도 실력이라고 생각하고 싶다...ㅎ

 

대회 과정은 아래 타임라인에서 자세히 설명하겠다. 

 

  2. 타임라인

 

[0:06] F 1WA → AC

 

djs100201이 해결한 문제이다. 5분쯤에 WA를 받고 수정해서 AC를 받았는데, 옆에서 "이걸 퍼솔을 못했네"라는 식의 말을 들은 것 같다. 

 

[0:11] B 3WA → AC

 

내가 푼 문제이고, 본 대회에서 가장 많이 풀리고 퍼솔이 3분 만에 나온 가장 쉬운 문제였는데, 3번이나 틀렸다. 쉬운 문제인 건 한눈에 봐도 알 수 있었지만, 퍼솔이 빨리 나와서 다급했던 부분이 있었고, 해서는 안될 실수를 너무 많이 했다. 사실 이때 대회 망했다는 생각도 들었고, 이미 페널티는 글렀다고 생각하고 문제수로 가자는 생각을 했다. 

 

[0:29] C 1WA → AC

 

내가 먼저 본 문제였는데, 풀이가 바로 떠오르진 않아서 넘겼었고, 자신이 맡은 문제를 모두 살펴본 후 볼만한 문제가 없냐던 djs100201에게 문제를 넘겼다. 

간단히 구할 수 있는 규칙이 있을 거라고 정도만 얘기를 했고, 그 말을 들은 djs100201이 우선 완탐으로 N이 작은 경우의 답을 모두 출력해보겠다는 말을 하고 코드를 구현했다. 평소에 나는 완탐으로 작은 케이스를 직접 돌려보는 방식을 사용해본 적이 거의 없는데, 실제로 많은 고수들이 사용하고 대회에서도 사용하는 모습을 보고 본받아야겠다는 생각이 들었다. 

그 결과, 규칙을 같이 발견했고 djs100201이 코드를 구현하는 과정에서 옆에서 검증해주었다. 규칙을 잘못 이해해서 1번의 WA를 받고 수정하여 AC를 받았다. 이때까지 압도적인 페널티를 유지하고 있었고, 사람들이 다들 잘한다고 느꼈다. 

 

[0:38 ~ 0:40] I 2WA

 

스코어보드 상 꽤 풀려있던 문제여서 내가 잡고 풀고 있었다. 그런데, 알고 보니 딸기와 토마도를 여러 번 심는 걸로 문제를 잘못 이해했었고, 먼저 WA를 받았다. 그리고 수정한 후에도 WA를 받았고, 구현 문제여서 자칫하면 말릴까봐 다른 사람에게 넘겼다. 사실 구현이 꽤 까다로웠는데, 되게 빨리 풀려있어서 많이 당황했다. 

 

[0:48] M AC (First Solved)

 

djs100201이 해결하였다. OEIS를 사용해서 해결한 걸로 아는데, 되게 빠르게 잘 해결한 것 같다. 

 

[1:14] I 3WA → AC

 

I번 문제를 넘겨받은 djs100201이 1번의 WA를 받고 AC를 받았다. 마찬가지로 구현에서 꽤 애를 먹은 것 같았는데, 다행히 해결하였다. 이때쯤 I를 거의 10팀은 풀었던 것 같은데, 너무 어렵게 생각했나 싶기도 하다. 

 

[1:20] J AC

 

구현 말린 I번 문제를 넘겨주고 나서 나는 J번 문제를 잡았고, 다행히 한 번에 AC를 받을 수 있었다. 풀이 방법이 되게 다양하다고 들었는데, 나는 좌표 압축 후 정렬한 뒤 펜윅트리를 이용하여 해결하였다. 

 

[1:33 ~ 1:45] E 3WA

 

J를 맞춘 후 djs100201과 함께 E에 붙었다. 입력 데이터를 거꾸로 살펴보면 될 것 같다고 내가 말했고, 항상 2배씩 커져야 한다는 등 여러 아이디어를 조합하여 코드를 작성했는데 WA를 받았다. 

 

[1:49 ~ 2:18] L 4WA

 

lem0nad3이 오랜 시간 동안 잡고 있던 문제였다. 나는 무슨 문제인지 알지 못했지만, 굉장히 긴 코드 길이와 함께 WA를 받고 있었다. 이후에 djs100201을 불러 풀이 아이디어를 다시 점검했다. 

 

[2:25 ~ 2:52] E 3WA → 8WA

 

djs100201이 L을 도와주고 다른 문제를 풀러 갔을 때, 나는 계속 E를 잡고 있었다. 이번에는 거꾸로 보면서 붙일 수 있는 정점의 최대/최소를 관리해가는 방식이었는데, 계속해서 23%를 뚫지 못하고 있었다. 다른 팀들도 무수히 많은 WA를 받고 있었어서, 코너 케이스가 많이 있을 것 같다고 생각은 했지만, 내가 떠올린 풀이에 틀린 점을 아무리 찾을 수가 없었다. 그래서 결국 더 말리면 안 될 것 같아 E를 우선 놓았고, 다른 문제를 보러 갔다.

 

[2:46 ~ 2:47] L 4WA → 5WA → AC

 

결국 lem0nad3이 L을 해결했다. 3000byte가 넘는 코드였는데, 잘 해결한 것 같다. 해결하자마자 내가 E 도움을 요청했던 기억이 있다. 

 

[2:55 ~ 2:56] K 1WA → AC

 

E 풀이의 틀린 점을 계속해서 찾지 못했고, 두 명이 붙으면 너무 말릴 것 같아서 내가 E를 잡고 djs100201은 다른 문제를 해결하러 갔었고, K를 해결했다. 퍼솔이랑 3분 차이밖에 나지 않았던 게 조금 아쉽다. 

3시간 후부터 프리즈가 되었고, 프리즈 때 8솔로, 최상위권 팀들의 솔브수가 비슷했다. 페널티가 많았기 때문에 1등을 하기 위해서는 최소 10솔은 해야겠다고 느꼈다. 

 

[3:48 ~ 4:01] H 2WA, 1RE, 1CE → AC

 

E를 푸는 도중에 계속해서 다른 문제들을 한 번씩 보았다. 그러던 중 H가 프리즈 이전에 풀려서 djs100201과 함께 H를 보았는데, 문제 스타일이 딱 LCP를 이용하는 느낌이었다. djs100201도 마찬가지로 매내처 + LCP로 가능할 것 같다는 의견이었지만, 나는 구현에 엄두가 안 났고, 다른 팀에서 꽤 빠른 시간에 풀어서 뭔가 생각하지 못한 쉬운 풀이가 있지 않을까 생각했어서 개인적으로는 조금 반신반의했었다. 

그래도 djs100201가 가능할 것 같다며 구현을 시작했고, 나는 E를 고민하면서 동시에 옆에서 H의 코드와 풀이를 계속 검토해주는 방식으로 진행하다가, E를 결국 lem0nad3에게 넘겨주었다. 내 풀이에서 도저히 틀린 점을 찾지 못해서 다른 아이디어가 있지 않을까 했고, lem0nad3이 E를 맡았고, 나는 H에 완전히 붙어서 함께 구현했다. 

꽤 오랜 시간 구현을 했고, 결국 예제가 나오는 것까지 성공했지만 WA를 받았고, 팰린드롬의 길이가 K인 것뿐만 아니라 K+1인 것도 고려를 해야 한다는 것을 발견해서 그대로 복사해서 하나 더 추가했고 결국 AC를 받았다. 

 

[4:16] A AC

 

H를 기분 좋게 해결하고, A를 보았다. 사실 A는 기댓값 문제여서 처음에 넘겼고, 팀 연습 때 기댓값 문제를 꽤 잘 풀었던 djs100201를 기다리고 있었다. 

대충 1500^3의 dp 풀이에서 시간을 줄일 방법을 생각하지 못했었는데, 먼저 특정 단계에서 다음 단계로 탐색하는 경우의 수가 최대 3개라고 djs100201에게 전달했고, 그 말을 들고 곧바로 2500^2로 dp를 줄일 수 있다고 알려주었다. 

기댓값 문제를 풀어본 경험이 거의 없어서 이 또한 구현을 부탁했고, 나는 옆에서 서포팅을 했다. 

이 문제는 골드 문제임에도 불구하고 퍼솔이 프리즈 이후에 나왔는데, 아마 기댓값 문제여서 일단 제쳐둔 경우가 많았던 것 같다. 우리 팀 또한 퍼솔이 계속해서 나오지 않아서 A를 굉장히 늦게 잡았다. 

 

[4:27 ~ 4:33] E 8WA → 12WA

 

페널티가 많아서 10솔로는 1등이 불가능하다는 것을 알았기 때문에 E를 무조건 풀어야 했다. 

그러던 중 E를 가져간 lem0nad3이 코드를 제출했는데, 그동안 계속 뚫리지 않던 23%를 뚫고 51%에서 WA를 받았다. 따라서 3명 모두 해당 코드를 가져와서 각자 코드를 살펴보기 시작했다. 

 

[4:38 ~ 4:51] E 12WA → 19WA

 

중간중간 틈틈이 반례도 찾고, 풀이를 수정해보기도 했지만 계속해서 51%를 뚫지 못했다. 

 

[4:57 ~ 4:59] E 19WA → 24WA → AC

 

종료 시간이 다되어 갔을 땐 찾은 반례를 예외 케이스로 따로 넣는 등 이미 페널티는 글렀기 때문에 셋 다 무지성으로 코드를 제출하기 시작했다. 약 3분 동안에 7번의 제출이 있었다. 

그러던 중 마지막에 반례를 하나 더 찾았고, 시간이 없었기 때문에 해당 반례를 직접 넣어서 예외 케이스로 처리를 해서 각자 제출하고 있었다. 최종적으로 제출한 시간은 4시간 59분 51초였고, 막판에 채점이 느려서 결국 대회 시간이 먼저 끝났고, 10솔로 1등은 실패구나 생각하고 반쯤 포기한 채 채점 현황을 기다리고 있었다. 

다들 대회가 끝나고 자리를 돌아다니고 있을 때, 마지막 제출 코드가 51%를 뚫었고 AC를 받았다. 너무 기뻐서 다들 소리를 쳤었는데, 학회실에 있던 모든 사람들이 AC를 받았다는 걸 알 수 있을 정도였던 것 같다. 

---

이렇게 기적처럼 11솔로 1등을 달성하게 되었다. 중간에 G도 살펴보고 구글링도 꽤 했었는데, 실제로 본 대회나 오픈콘에서 검색으로 해결한 케이스가 많아, 아쉬움이 있긴 하다.

서강대가 suapc를 계속해서 우승해오고 있긴 하지만, 연대와 홍대에도 충분히 1위를 할 수 있는 팀이 있기 때문에 올해 icpc에서 좋은 경쟁을 할 수 있을 것 같다. 다음 주가 icpc 예선인데, 좋은 결과를 얻었으면 좋겠다.