2021 SUAPC Summer 동상(6위) 후기

6등!

먼저 허접한 나의 실력으로 동상을 받게 해준 pgggggggggh kckc0608에게 감사의 말을 전한다.

팀빌딩

SUAPC 팀을 구하지 못해 대회 신청 기간이 되어서야 부랴부랴 인원을 모았다.

ㅋㅋㅋㅋ 맨 처음에는 완전 어색했지만 팀연습하면서 친해지고

히딩크 전술으로 말도 놓게 되면서 편해지게 되었다.

C. 조각 체스판 1CE 1TLE (11분)

먼저 C는 kckc0608이 잡았다.

모든 칸에 대해서 검사하는 식으로 진행했는데 O(N^2M^2)이라 시간초과가 났다.

 

컴파일 에러는 python으로 적었는데 C++로 제출해서 퍼스트 컴파일 에러를 받았다 ㅋㅋ

 

F. Flat Earth AC (13분)

A번을 보고 있다가 F가 많이 풀리길래 바로 F로 달려왔다.

전형적인 코포 A번이라 바로 짠 뒤에 내서 AC를 받았다.

이걸 낼 때 다른 팀들이 D, F 2솔이 많아서 바로 D를 풀어야 한다는 압박감이 있었다.

 

C. 조각 체스판 1TLE 1WA (1시간 8분)

kckc0608이 시간초과 코드에서 약간의 최적화를 하고 다시 제출해봤지만 시간초과를 받았다.

다 검사해줄 필요가 없다는 걸 알아내고 dp로 세로와 가로를 처리해 min(가로, 세로)를 출력했지만 WA를 받았다.

사실 대각선까지 검사해주었어야 했는데 이 점을 알지 못하고 다른 문제로 이동했다.

 

A. 휴먼 파이프라인 1WA  AC (81분)

A를 봐달라는 요청에 kckc0608이 A를 잡았다.

정렬한 후 O(1)로 최적을 판단하여 답을 출력했는데 WA를 받았다.

그 후 틀린 이유를 찾아봤는데, 최댓값으로 잡은 수가 정답보다 작아 문제가 되는 것이었다.

최댓값을 크게 설정하고 다시 제출하니 AC를 받았다.

 

시작하고 1시간 21분이 지났을 때 2솔을 했더니 19등이었다.

C, D를 빨리 풀고 4솔로 올라가자고 했다. 급한 마음으로 D를 잡았다.

 

C. 조각 체스판 1WA  2TLE (2시간 31분)

내 실수로 반례를 넘겨주지 못하고 pgggggggggh에게 C를 dp로 풀어달라고 했다.

WA를 받고 반례를 해결할 방법을 찾다보니 풀이법이 떠올랐다.

내가 다시 C를 잡아 반례를 통과하는 코드를 짰다.

첫 제출 때 26%까지 올라가는 것을 보고 통과했다고 생각했으니 시간초과가 떴다.

pypy의 문자열 비교연산으로 인해 TLE를 받았다고 생각한 나는

문자열을 리스트로 바꿔주었으나 이번엔 2%에서 시간초과가 떴다.

 

아무리 생각해도 O(NM)이었기 때문에 파이썬이 파이썬했다고 믿고 C++로 짜서 제출했다.

아슬아슬하게 816ms로 AC를 받았다.

 

2시간 반 3솔이라 정신적으로 많이 힘들었고 남들이 다 푼 D번을 못풀었다는 것에 목메여서 D번에 시간을 버렸다.

 

H. 재활용 캠페인 3TLE (3시간 2분)

kckc0608가 H를 잡았다.

kckc0608의 풀이는 투포인터 역할을 하는 deque를 사용하고, 이분탐색으로 lowerbound를 구해 매칭을 해 주었다.

풀이는 맞는 것 같았는데 중간에 있는 애를 지우기가 힘들었다.

del을 사용하면 O(N^2)이라 시간을 줄일 방법을 계속해서 찾아보고 있었다.

 

2시간 남기고 내가 했던 말이 기억나는데, 

우리가 2시간동안 각자 한문제씩 풀면 6솔이니까 2시간동안 3문제를 푼다고 생각하지 말고

2시간동안 한 문제 푼다는 마인드로 가자며 아모른직다를 시전했었다.

 

E. 문자열 조작의 달인 AC (3시간 21분)

갑자기 pgggggggggh가 E번 제출한다고 하더니 채점 %를 계속 말해줬다.

한 50%까지 올라갔을 때 맞았음을 직감했다.

한 번의 제출로 AC를 받고 다들 다시 기운이 살아나는 계기가 되었다.

 

그 후 내가 D번을 무조건 풀테니 pgggggggggh와 kckc0608에게 H를 풀어달라고 말했다.

 

D. 반짝반짝 2 AC (4시간 8분)

dp로 접근을 했었는데 아무리 해도 예제도 제대로 나오지가 않았다.

무턱대고 하면 안 될 것 같아 고등학생때 배웠던 확통책을 가져와 확률변수를 계산해봤었다.

근데 그래도 안나와서 정말 초심으로 돌아가 3줄 무지성 코딩을 했다.

예제2가 제대로 나오는 것을 보고 제출했더니 AC를 받았다.

 

이제 5솔을 찍을 때 정말 6솔을 하면 입상 가능성도 있겠다고 생각을 해서 바로 H로 넘어갔다.

 

H. 재활용 캠페인 3TLE 6WA AC (4시간 48분)

거의 kckc0608가 짜둔 코드를 변형해서 제출하는 식으로 진행했다.

kckc0608는 시간을 더 줄이는 코드를 짜고 있었고, pgggggggggh는 python으로 작성된 코드를 C++로 바꾸고 있었다.

나는 그냥 그리디를 무지성제출 하고있었다.

 

그리디를 제출하면서 모두에 2를 곱하면 실수연산을 할 필요가 없다는 사실을 알고 알려줬다.

 

20분 남았을 때, 나는 이제 거의 포기하고 K번이나 보고있었다. ㅠㅠ

그리고 8분 뒤 갑자기 pgggggggggh가 채점이 돈다고 말하자마자 바로 모두 소리지르고 난리도 아니었다.

총 13트만에 AC를 받고 프리즈 이후 2솔을 해냈다.

 

스코어보드 공개

스코어보드는 홍익대학교의 생수팀과 같이 구경했다.

즐겁고 유익한 1시간 30분가량의 기업세션 이후에 스코어보드가 공개됐다.

 

우리의 프리즈 전 순위는 16위, 입상은 하고싶었기에 최소 10등 이내에 들었어야 했다.

프리즈 이후에 푼 D번이 공개되었을 때 11등으로 올라갔다.

우리가 쌓은 패널티가 매우 많았기 때문에(1300) 동일 솔브가 있으면 후순위가 되는 건 당연했다.

6솔브가 없기를 빌며 계속 스코어보드 시청을 이어갔다.

 

프리즈 이후에 푼 H번을 공개할 때 우리의 순위는 14위였다.

우리의 H가 공개되었을 때 6등까지 올라가는 것을 보고 

어? 이러면 동상을 받을수도 있겠다! 라는 생각은 하나도 들지가 않았고

잘하면 장려상을 받을 수 있겠다는 생각을 했다.

 

점점 다른 팀들의 프리즈 이후 제출이 공개가 되고 8등의 제출이 공개되었을 때

동상을 받을 수도 있겠다 생각이 점점 들었다.

 

마지막 7등의 제출이 공개가 되고 6등이 확정이 되었을 때 개 난리를 쳤던 것만 기억난다.

 

마치며

일단 동상을 받아 기분이 정말 좋았지만

내가 더 잘했으면 스코어보드를 보며 기도할 필요가 없었을텐데 라는 생각이 들어 아쉽기도 했다.

 

목표였던 동상을 얻어 정말 기분이 좋았고

이번에 같이 팀을 했던 pgggggggggh kckc0608와는 휴학하고 군대를 다녀온 뒤

icpc를 같이 나가자는 약속을 했다.

 

좋은 대회를 기획해준 ICPC Sinchon, 좋은 문제를 만들어준 출제진 및 검수진 분들,

대회가 원활히 개최될 수 있게 해준 후원사들에 감사의 말씀을 드리고,

2주 전에 팀빌딩했지만 좋은 결과를 보여준 우리 팀원들에게 마지막으로 감사의 말을 전하고 싶다.

 

끗