SUAPC 2021 Winter 대회 후기

 

 

2021 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter)에 참가하였다. 

 

No Orange cant win (weasel, rhksdn6227, Rebro) 이라는 팀으로 참가하여 은상(3등)을 차지하였다. 

저번 주에 있었던 Camp contest에서도 은상을 받았는데, 콩의 기운이 맴돈다...

 

페널티의 소중함

 

2등과의 차이가 고작 페널티 7분 차이이다. 1WA만 덜했다면 :(

다행히 3등까지 은상이기 때문에 그나마 아쉬움이 덜 했지만, 상의 색이 달라지는 등수였다면 매우 매우 아쉬울뻔했다.

대회 중간에 한동안 1등과 솔브수가 같아서 혹시나 꺾을 수도 있겠다는 생각을 했는데, 역시나 괜히 월파팀이 아니다. 

(선생님들은 이제 제발 출제진으로 가주세요....)

 

팀명을 정할 당시만 해도 weasel이 퍼플이었고, 롤이라는 게임에 관심이 많다면 알 수도 있는 "4 chinese can't win"을 인용해서 팀명을 만들었는데, 그 후 며칠이 지나지 않아 곧바로 weasel이 오렌지를 찍어버렸다!

 

오렌지의 탄생이 Orange can win의 복선이 아닐까 하는 실낱같은 희망을 가졌지만 어림없었다. 

사실 1, 2등 팀에도 오렌지가 있으니 Orange can win이 틀린 말은 아니긴 하다. 

 

문제 난이도는 다음과 같다. (21.03.02 12:00 기준)

C번과 F번이 골1과 플5를 왔다 갔다 하는 중이다. 

난이도 분배는 꽤 잘 되었다고 생각한다. 하위권들도 적절히 해결할 수 있으면서, 상위권을 위한 변별력도 충분히 갖춰져 있다. 

좋은 문제들을 만들어준 출제진과 검수진분들에게 감사의 말씀을 전하고 싶다. 

 

문제와 해설은 아래의 링크에서 확인할 수 있다.

 

문제 : www.acmicpc.net/category/detail/2446

 

해설 : upload.acmicpc.net/da622589-3a29-48a1-9e6c-2a71fa2887ce/

---

[팀 결성]

 

팀의 결성은 weasel에 의해서 이루어졌다. 

지난 대회 때 온라인으로 참가하는 것의 민폐와 단점을 많이 느꼈고, 그렇다고 서울에 올라가기엔 난감한 상황이라 혼자 참가할 수 있다면 혼자 참가하거나 참가하지 않을 예정이었다. 

 

그 와중에 졸업으로 떠나는 줄 알았던 weasel의 연락을 받았고, 생각지 못한 수준 높은 팀을 만나게 되었다. 

나를 제외한 2명은 모두 이미 취업을 한 졸업예정자여서 대회를 같이 할 수도 있는 사람으로 생각도 못했기 때문에 든든함과 동시에 1인분이라도 하려면 더 열심히 해야겠다는 생각이 들었다. 

사실 rhksdn6227은 이전까지 모르는 사이였는데, 대회 후 뒤풀이에서 알게 된 사실로는 서로 모르지만 각자 서로의 성장에 대해서, 특히 코포 레이팅에 있어서 엄청 신경을 쓰고 스트레스를 받고 있었다 !ㅋㅋ 

결과적으로 성장의 원동력이 되기도 했지만, 역시나 코포는 정신건강에 해롭다. 

 

지금 생각해보면 셋 다 수학과이고 컴공 복전에 뒤늦게 PS에 입문한, 공통점이 나름 많다...^^ 이거만 보면 은상도 되게 잘한 게 아닐까?라고 합리화하고 있다. PS를 통해 받는 스트레스를 줄이자...

 

처음 팀을 이룰 때는 온라인으로 참가해도 괜찮냐는 양해를 구했고 OK를 받아서 팀에 합류했는데 준비하는 과정에서 욕심이 더 생겼고, 그래도 대회는 오프라인으로 진행하는 게 낫지 않을까 해서 너무 고맙게도 형들이 부산으로 내려와 주었다. 약간 대회 반 여행 반의 느낌이었는데 오랜만에 대학 사람들을 만나서 여행 같은 느낌을 받으니 너무 좋았다. 

 

---

[준비 과정]

 

팀 연습은 1월부터 주 1회씩 진행했다. 

온라인으로 진행했기 때문에 줌(zoom)을 통해서 연습했는데, 화면 공유로 그림판이나 코드를 통해 설명하는 건 생각보다 많이 어려웠다. 대회를 온라인으로 진행했다면 결과가 안 좋았을 것 같다.

 

처음 3~4번 정도는 직접 셋을 골라서 우리끼리 진행을 했고, 이후에는 학회에서 진행하는 연습셋을 통해서 다른 팀들과 함께 팀 연습을 진행했다. 

SUAPC 문제가 한글 지문으로 나오기 때문에 한글 셋으로만 연습을 하려고 하였고, 그러다 보니 적절한 셋을 찾기가 쉽지는 않았다. 

다행히 학회에서 연습셋을 진행해 주어서, 셋을 선택하는 어려움이 해결되었고 또 다른 팀들과 함께 진행하는 게 혼자 진행하는 것보다 훨씬 연습에 도움이 많이 되었다.

 

처음 몇 번은 문제 풀기 -> 푼 문제들 리뷰 -> 못 푼 문제 해설 참고로 단순하게 진행했다. 그러다 보니 팀으로서 더 발전한다는 느낌이 적었고, 이후에는 셋을 돌고 나서 팀적인 피드백을 조금씩 해나갔다.

회의를 통해서 각자 문제를 읽고 몇 분 이후에 문제 설명을 한다던지, 구글 닥스에 요약을 한다던지, 한 문제에 말리면 어떻게 해결해 나갈 것인지, 유형과 난이도별로 어떤 사람이 맡는다던지 등등을 조금이나마 맞춰나갔다. 

사실 팀 연습 과정에서 심각하게 말리거나 못한 경우가 딱히 없었어서 오히려 본 대회를 더 걱정하기도 했는데 결과적으로는 연습 때와 비슷하게 흘러간 것 같다. 

 

개인적으로는 문제 해결 능력이나, 알고리즘 습득에 힘을 썼다. 

다른 팀원들이 PS에 몰두할 수 있는 상황이 아니었고, 2달 동안 열심히 하겠다는 마음가짐과 함께 신촌 연합 겨울 캠프라는 좋은 기회가 있었기 때문에 최대한 다양한 알고리즘에 대해서 공부를 하려고 노력했다. 실력은 다들 이미 뛰어나니, 나는 지식적인 측면에서 팀에 도움이 되기를 바랐다. 물론 대회 때 새로 공부한 알고리즘으로 푼 문제는 없었지만... 그래도 꽤나 비약적인 성장을 한 것 같다.

 

---

ICPC 준비를 위한 대회였기 때문에 5시간에 13문제로 대회가 진행되었다. 

처음에 weasel형이 A~E , rhksdn6227형이 F~I, 내가 J~M을 읽었다. 편의상 팀원들을 핸들로 부르겠다.

(착한 형들이니 이해해주리라 믿는다 ㅎㅎ)

 

[타임라인]

 

[00:06] B 1WA / I solved

 

문제를 읽던 도중, I 퍼솔이 2분쯤에 나오는 걸 보고 곧바로 내가 rhksdn6227에게 I가 풀렸다고 알려주었다. 

그래서 rhksdn6227이 I를 먼저 읽고 풀이를 떠올려서 코드를 짰는데 너무 간단해서 풀이에 확신이 없다고 했다. 

페널티에 대해서 조심스러워했는데, 그 당시에 I가 5팀 넘게 풀려있어서 맞을 거라는 확신을 주었고 조용히 B에서 1WA를 받은 weasel을 보고 바로 제출했다고 한다. 다행히 AC를 받았다. 

다시 문제를 보니 코포 A번 문제 같은 느낌이다. 

 

 

[00:09] B solved

 

weasel이 해결하였다. B 또한 3분에 퍼솔이 나와서 내가 B도 풀렸다고 알려주었다. 

문제가 뭔지 모르지만, 뭔가 잘못 생각한 부분이 있다고 했고 고쳐서 금방 해결했다. 

 

 

[00:32] H 2WA -> solved

 

내가 J ~ M 을 먼저 읽었을 때, J는 어려워 보였고, K, L은 이해는 됐는데 풀이가 확 떠오르진 않아 뭔가 말릴 듯한 느낌이었고, M은 다 읽지도 않고 넘겨서 다른 팀원에게 풀만 한 거 없냐고 물어봤다.

그때 rhksdn6227이 I를 풀고 F를 보느라 G, H를 못 읽어서 내가 H를 읽으러 갔다. 

문제를 처음 보고 기하문제인줄 알았으나, 알고 보니 직선의 기울기만을 이용하는 단순한 문제여서 코드를 짰는데, 직선이 y축 또는 x축에 평행한 경우(a == 0 || b == 0)를 잘 따지지 못해서 2WA를 받았다. 

결국 weasel에게 내 풀이 검증을 요청했고, 같이 예외 케이스들을 생각해보며 AC를 받았다. 

 

H AC를 받기 직전에 스코어보드상에서 우리 팀이 10등 안에도 들지 못한 상태였기 때문에 순간 망했다는 생각을 했었다. 이미 페널티를 많이 쌓아서 이 시점부터는 페널티에 크게 신경 쓰지 말고 푼 문제수로 승부를 보자고 의견이 모아졌다. 

그래도 1틀만 덜 했다면.....

 

그 후 weasel은 L, rhksdn6227은 F, 나는 K를 잡고 있었다. 

다들 풀이가 생각났다고 했고, 1문제씩만 풀면 바로 6솔로 올라가고 아직 1시간도 안됐으니 천천히 하자고 서로 얘기했다. 

 

 

[00:48] F 2WA -> solved

[00:49] L solved / K 2WA

 

이전에 F 2WA와 K 1WA를 받은 상태에서 놀랍게도 48분경에 셋다 거의 동시에 '예제가 나온다'라는 멘트와 함께 순서대로 제출을 했다. F와 L이 AC를 받고 나만 WA를 받았다 ㅠ

F는 아직 어떤 문제인지는 모르고 L은 내가 처음 읽고 나서 BFS 유형 같으면서 풀만한 문제라고 weasel에게 넘겼는데, 폭탄을 놓을 수 있는 위치에 모두 놓으면 되는 애드혹 문제라는 답변이 돌아왔다. 역시 오렌지의 관찰이란....!

 

 

[00:56] K solved

 

처음에 K를 읽을 때에는 제일 작은 합성수부터 나누었을 때, 나머지가 0이면서 몫 또한 합성수이면 나눠가는 식으로 나이브하게 구하면 어떨까라는 생각이 들었지만, N이 10^12이므로 몫의 범위 또한 크기 때문에 몫이 합성수인지 판단을 어떻게 하지 생각이 들었다. 

혹시나 하는 생각에 그냥 밀러-라빈을 박을까?라고 weasel에게 물어봤는데 생각보다 바로 OK라는 답변이 나와서 코드를 짰다. 

스코어보드 상에서 K solved가 꽤 있어서 밀러-라빈이 정해가 아닌 건 둘 다 너무 잘 알고 있었지만 오버킬이라도 해서 문제를 풀자는 마인드로 구현을 했는데 2 WA를 받았다. 

지금 생각해보면 밀러-라빈이 문제가 아니라, (밀러-라빈을 이용하려면 __int128을 사용해야했다....) 같은 합성수로 여러 번 나눌 수 있다는 걸 빼먹어서 틀렸던 것 같다. 

L을 풀고 돌아온 weasel이 잠깐 생각해보더니 소인수분해해서 앞에서부터 2개씩 묶으면 된다고 알려주었고, 곧바로 코드를 짜서 AC를 받았다. 

 

이 시점에 단번에 2등으로 올라섰고, 1시간 만에 6솔을 달성해서 심적으로 조금 편안해졌다. 그다음으로는 weasel이 J, 내가 C, rhksdn6227이 A를 잡았다. 

 

 

[01:19 ~ 01:45] C 1RTE, 2TLE, 1WA

 

DP 풀이는 꽤나 빠르게 떠올렸다. 하지만 예제가 잘 나오지 않았고, 풀이를 다시 잘 살펴보니 기댓값을 계산할 때 전구가 끝나는 지점을 계산할 때에는 식이 조금 달랐다. 

그래서 이를 고려하니 예제가 잘 나왔고, 처음엔 배열 크기를 잘못 잡아 RTE를 받고 그다음은 TLE가 발생했다. 

분명 O(KN^2) DP로 해결했는데 시간 초과가 발생해서 한동안 고민하다가 J를 잡고 있던 weasel에게 잠깐 코드를 봐달라고 하고, bottom-up으로 다시 구현했다. weasel은 혹시 곱셈 연산이 오래 걸리지 않을까 싶어서 전처리를 해두라고 하였고, "일단 bottom-up으로 한번 해보고 그래도 TLE가 나면 전처리를 해둘게"라고 말해두고 bottom-up으로 구현해서 제출했는데 웬 WA가 나왔다. 

도저히 모르겠어서 다시 이전에 짠 top-down 코드로 돌아가서 전처리를 박았는데 여전히 TLE가 발생했다. 

이때부터 멘붕이 시작됐다. 아무리 봐도 맞는 코드 같은데 TLE는 왜 발생하는지 이해가 안 됐다. (아직도 모른다)

 

 

[01:55] J 4WA -> solved (First solve)

 

우리 팀의 선장 weasel이 J 퍼솔을 받아왔다!

내가 J를 읽고 요약을 했을 땐 세그트리를 통해 구간의 min, max를 관리하는 방식 같다고 적어두었는데, 완전 다르진 않지만 푸는 방법이 많이 달랐다. 내가 잡았다면 많이 손해를 볼 수도 있었는데 잘 건너뛰었고 weasel이 잘 해결했다. 

 

 

[02:11] C solved

 

J를 푼 weasel이 C에 합류했다. 

일단은 TLE는 도저히 해결 못하겠고, bottom-up은 그래도 WA이니 bottom-up에서 틀린 부분을 찾자고 생각했다. 

둘 다 한동안 틀린 점을 못 찾고 나는 코드만 보며 멍 때리고 있다가, 문득 예시가 떠올라서 넣어보니 답이 나오지 않았다. 

이전에 불가능한 경우에 대해서도 dp를 갱신을 해주는 오류가 발생하고 있어서 dp배열을 모두 -1로 초기화한 후 가능한 dp >=0인 경우에 대해서만 갱신을 해나가는 방식으로 수정하여 AC를 받았다. 

너무 오래 C를 고민해서 머리도 아프고 맥이 빠지는 기분이었다. 

 

 

[03:22] A solved

 

C를 해결하고 얼마 지나지 않아 A를 계속 잡고 있던 rhksdn6227이 아이디어는 떠올렸지만 구현을 못하겠다는 SOS 신호를 보냈고 weasel과 rhksdn6227이 함께 A를 풀기 시작했다. 

나는 남은 문제 중에서 그나마 한 팀에 의해 풀려있던 G를 잡았고, 옆에서 열심히 A를 해결하고 있었다. 이미 A의 풀이 아이디어는 나와있던 상태여서 구현하느라 애를 많이 먹은 것 같은데, 그래도 우여곡절 끝에 1트만에 A를 풀었다. (버스 승차감이 좋다)

9솔을 달성하고, 하나만 더 풀자는 생각으로 weasel은 E를, rhksdn6227과 나는 G를 잡았다.

 

 

[~04:00] 

 

G에 대해서는 정말 많은 아이디어가 나왔는데, 대회 초반에 weasel이 읽고 언급했던 2-sat이 그나마 제일 근접했다. 

하지만 그래프를 모델링하는 게 너무 어렵기도 했고, 각 정점별로 가능한 값이 너무 많다고 생각해서 2-sat이 안될 거라고 판단을 해버렸다. 사실 대회가 끝나고 풀이를 들었을 때도 이건 절대 못 떠올릴 것 같으면서, 떠올리더라도 구현을 못할 거란 생각이 들었다. 푼 팀들이 대단했다. 

그다음으로는 내가 오랜 시간 동안 생각하던 BFS 풀이가 있었는데, 어림없었다. 차라리 그 시간에 최근에 공부했던 MCMF 유형인 M을 한 번이라도 읽어나 봤으면 하는 생각도 든다. 

G가 프리즈 이전에 퍼솔이 나와서 이 문제가 다이아 문제일 줄은 상상도 못 했고, 퍼솔이 나오면서 이 문제에 더 집착을 하게 되었다.

그리고 rhksdn6227이 제시한 Maximum flow 풀이도 있었는데, 이 풀이는 사실 내가 극구 반대했다.... 만약 그 풀이가 맞았다면 두고두고 미안했을 것 같다. 정점이나 간선의 개수가 너무 많다고 판단했고, 직접 배열의 값까지 출력을 해주어야 했으므로 혹시나 풀이가 맞더라도 구현하기는 자신이 없었다. 

 

 

[04:16 ~ 05:00] E 3TLE

 

E를 오랜 시간 고민하던 weasel의 첫 제출이 TLE가 났다. 이 결과는 어느 정도 예상한 결과라고 하면서 아무것도 못하고 있던 우리에게 코드를 보여주었고, 어느 부분에서 줄여야 할까 같이 생각하다가 별다른 성과를 얻지 못하고 다시 떠났다. 그러다가 종료 직전에 80% TLE라는 절망적인 결과를 받고 울부짖는 weasel을 볼 수 있었다. 한 검수진의 멘트로는 자신의 풀이가 정해와는 달랐고, 우리 팀의 풀이가 해당 검수진과 비슷했다고 하는 걸 보니 시간이 조금 더 있었다면 컷팅으로 TLE를 해결할 수도 있지 않았을까 싶다. 정해는.... 알고 싶지 않다...

 

이쯤에 rhksdn6227이 G를 DP로 푸는 아이디어를 제시했는데, 꽤 괜찮다고 생각해서 코드 구현을 시작했다. 근데 이미 나는 번아웃이 된 상태여서 머리가 제대로 돌아가지 않았고, 어떻게 구현할지 알려달라고 하여 불러주는 대로 코딩을 했다. 얼추 비슷하게 답이 나오긴 했지만 올바르게 나오진 않았고 예제 2번을 해결할 방법을 알 수 없었다. 이미 이 상태에서 대회 시간이 거의 다 되어서 사실상 포기상태였다. 

 

대회가 끝나고, 스코어보드상으로 2~3등 정도 예상했었다. 사실 밑의 팀들의 스코어보드에서 종료 직전에 스코어보드 오픈 재미를 위한 제출들이 박히는걸 실시간으로 보고 있었어서 어느 정도 예상은 했다. 

 

---

[마무리]

 

2달 동안 열심히 준비했던 Camp Contest와 SUAPC가 모두 끝났다. 

두 대회 모두 아쉬우면서도 만족할만한 성과를 거두어서 크게 미련은 남지 않는다. 제대로 준비하고, 제대로 대회를 치른 게 처음이라 재미도 있었다. 이 맛에 팀 대회를 나가는 건가 싶다.

요즘의 제 1목표가 '스트레스 받지 않는 PS'이기 때문에 나도 모르게 합리화하는 건지는 모르겠으나, 겨울 캠프 이전의 실력과 비교하면 많이 발전한 기분이 들어서 다행이다. 오히려 목표가 사라져서 PS에 대한 의욕을 완전히 잃어버릴까봐 걱정이다...

 

신촌 연합을 이끌어주시는 분들에게는 항상 감사하다. 여름과 겨울 캠프가 없었다면 지금의 수준은 생각도 못할 것 같다. 그리고 개인적인 친분이 있지 않고 오직 PS라는 연결고리 하나만으로 응원해주시고 좋게 봐주시는 분들이 생각보다 많아서 다들 너무 감사하다. 혹시 나도 포함인가?라는 생각이 드신다면 맞습니다. 정말 정말 많은 힘이 되었습니다.

또 종종 조언을 구하거나 질문을 하시는 분들이 계신데, 답변하기엔 과분한 수준이지만 나 또한 그 시절을 너무 잘 알기 때문에 얼마든지 물어보시면 최대한 도움을 드릴 예정이다. 편하게 물어보세요 :)

 

뭔가 쓰다 보니 탈알고를 하는 사람이 된 듯한데, 많이 언급해온 대로 앞으로는 지금까지 PS에 해온 노력만큼은 하지 않을 예정이고, 또 그렇게 계속 못할 것 같다. 아마 코포는 꾸준히 하고 PS는 적당히? 1년만 해도 살짝 지치는 감이 있는데 갓들은 어떻게 수년을 열심히 하는지 대단하다... 지친다는 느낌이 든다는 게 그만큼 열심히 해온 것이라고 생각하고 싶다.

물론 또 다른 대회에 참가한다면 얘기가 다를 수도 있다. (Orange can win으로 여름에도 다시...?)

 

다른 개발 공부나 CS 공부 등에 많이 투자를 할 예정이다. 살면서 이렇게 배우고 싶은 게 많은 적이 없었고, 앞으로도 아마 없을 것 같다....ㅋㅋ 1년 가까이 PS만 주구장창 하니 더 그런 것 같다. 블로깅도 이제 자주 하고 몸 관리도 좀 하자...