2021 ICPC Sinchon Winter Algorithm Camp Contest 참가 후기

 

2021 ICPC Sinchon Winter Algorithm Camp 중급 Contest를 참가하였다. 

 

성적은 2등(은상)을 차지했다.

 

 

문제와 해설 링크는 다음과 같다.

 

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

 

해설 : www.acmicpc.net/board/view/64488

 

 

 

사실 최근에 머리도 잘 안 돌아가고, 문제 풀이에 대한 자신감이 매우 낮아져서 수상권에 못 들어갈 것 같다는 생각이 머릿속을 지배하고 있었다. 

분명 할 수 있는 최대한으로 1~2월을 열심히 해왔는데, 그래서 그런지 대회 직전에 번아웃이 왔던 것 같다...

최근 폼이나, 객관적인 실력으로도 3~4등 정도라고 생각해서 3등으로 수상만 하기를 바라며 대회에 참가했다. 

(나를 제외하고 1오렌지, 1퍼플이 있었으며 근래에 뛰어난 성장을 보여준 사람도 몇몇 있었다. 잘하는 사람이 너무 많다.)

 

그래도 다행히 2등을 차지해서 조금이나마 마음이 놓이게 되었다. 

해봤자 캠프 모의고사에 불과한 대회일 수는 있지만 나에겐 생각보다 긴장되고 부담이 많이 되는 대회였다. 

 

여름 캠프가 끝난 이후인 9월부터, 나름대로 많은 성장을 해왔다고 생각하는 반년의 기간이 지나고 처음 맞는 대회였기 때문에 뭔가 보여줘야 한다는 부담감도 있었고, 주변에 빠르게 성장하는 사람들을 보며 밀리면 안 되겠다는 압박감도 있었다. 

또, 1주일 뒤에 있을 SUAPC 대회의 전초전 같은 느낌도 살짝 있어서 SUAPC 팀원(weasel, rhksdn6227)들의 잘하라는 압박(?) 같은 응원도 있었기에 많은 욕심이 있었다. 

 

물론 모든 참가자들이 그렇겠지만, 충분히 더 좋은 성적을 거둘 수 있었던 대회였기 때문에 아쉬움도 남은 대회이다. 

 

---

[타임 라인]

 

[00:02] A solved (First solve)

 

대회의 시작을 기분 좋게 만들어준 A 퍼솔이었다. 

문제를 보고 O(N) 풀이가 바로 떠올라서 빠르게 AC를 받을 수 있었다. 

사실 위에서 말했듯이 자신감이 많이 없어서 어차피 난이도 순으로 문제가 이뤄졌으니 1시간 동안은 스코어보드를 보지 말자는 생각이었는데, 첫 문제 잘 풀리니 금방 보게 되었다.

N이 4000 정도라 N^2 풀이도 있는데, 개인적으로는 O(N) 풀이가 훨씬 간단하다. 

counting inversion 문제는 워낙 유명한 유형이라 조금 접해본 사람이면 생각하기 어렵지 않을 것 같다.

 

 

[00:10] B 1 TLE

 

처음엔 DP로 접근을 했다. 

사실 DP가 안될 것 같다는 게 눈에 너무 잘 보였는데, 당장에 다른 풀이가 전혀 안 떠올라서 혹시나 하고 DP로 짜서 제출했는데 역시나 TLE가 났다. 

그러고 조금 더 고민하다가 넘기려던 찰나에 한두 명씩 B 솔브가 나오는 걸 보고 잠깐 더 잡았다가 일단 넘겼다.

 

 

[00:49] C 1 WA

 

인터랙티브형이 왜 여기서 나와...?

이 사이에 엄청난 방황을 했다. 2등을 하게 된 결정적인 이유가 아닐까 싶다. (물론 못 푼 내 잘못이다..) 

B에서 말려서 C로 넘어갔는데 갑자기 인터랙티브 문제가 떡하니 나와있다. 

개인적으로 인터랙티브 문제에 되게 취약하고, 또 캠프 모의고사인데 얘가 왜 있지? 하는 생각과 함께 당황한 나머지 B와 C와 D를 왔다 갔다 하면서 이도 저도 아닌 상태가 되어버렸다. 

그 사이 B 솔브들이 쭉 채워져서 5~6등으로 밀려났고, 살짝 멘탈이 나간 상태로 C를 풀었다. 

인터랙티브가 디버깅이 되게 힘들어서 믿음의 제출을 해야 하는데, 첫 시도에서 WA를 받아서 시간이 많이 뺏길 것 같다는 직감으로 바로 D로 넘어갔다. 

 

 

[01:04] D solved (First solve)

 

이전에 D를 잠깐 읽었을 때, 분명 Union-find 문제는 너무 자명하고, 스위핑도 떠올렸는데 구간들을 합치는 과정이라 구간이 겹치는 부분을 어떻게 빠르게 처리할지를 몰라서 못 풀고 다시 C로 돌아갔다. 

C에서 WA를 받고 스코어보드에는 이미 3 솔브가 찍혀있어서 망했다는 생각으로 D로 왔는데 겹치는 거 하나만 연결하면 결국 다 연결되겠다는 아이디어가 바로 떠올랐다. 

어떻게 보면 Union-find의 기본적인 아이디어인데 바보 같았다... 

그래서 바로 set을 이용해서 빠르게 풀어내었다. 

 

 

[01:24] E solved (First solve)

 

문제를 대충 읽고 LCA 문제 같아서 바로 LCA 코드를 복붙 해온 뒤에 다시 문제를 자세히 읽어봤는데 LCA를 구할 필요가 없었다. LCA에 이용되는 아이디어 (Sparse table)만 이용해도 충분해서 다시 코드를 다 지우고 구현해서 제출했는데 운 좋게 1트만에 맞았다. 

이때까지만 해도 아직 3등 정도여서 머릿속엔 B와 C만 맴돌고 있었다. 

 

 

[01:38~01:39] F 2 RTE 

 

정말 멍청하게 배열 크기를 잘못 잡아서 런타임 에러가 2번이나 났다... 카드 한 장을 미리 빼놓고 계산한다는 생각에 배열 크기도 하나 덜 잡았다. 그냥 넉넉하게 배열을 잡았으면 될걸 괜히 타이트하게 잡다가 페널티를 많이 쌓았다.

 

 

[01:40] F solved (First solve)

 

Bit DP를 많이 풀어 본 사람이면 문제를 읽고 Bit DP 문제라는 걸 꽤 쉽게 떠올릴 수 있을 것 같다.

백준에서 '박성원' 문제랑 비슷한 느낌이고, 다행히 풀이가 빠르게 생각나서 꽤 금방 해결할 수 있었다. 

D, E, F를 50분 정도만에 해결하고 이 당시 2등으로 올라서서 이때 마음이 조금 편해졌던 것 같다. 

어찌 됐든 문제가 난이도 순으로 정렬이 되어있다고 알려져 있고, 뒷문제를 내가 먼저 풀었으니 유리하다고 생각했다. 

 

 

[01:50] B solved

 

F를 풀고 화장실에 갔다. 잠깐 볼일을 보면서 B의 DP 풀이에서 뭘 해야 시간이 줄어들까 생각을 해보니 어차피 이동할 수 있는 최대 범위 이내의 모든 위치는 이동이 가능하므로, 최대한 멀리 갈 수 있는 칸으로 이동하면 다른 칸을 간 것보다 못하지는 않겠다는 생각이 딱 들었다. 

'DP가 아니라 그리디구나' 생각이 들자마자 빠르게 손을 씻고(?) 컴퓨터로 달려갔다. 

예상대로 그리디 문제가 맞았고, AC를 받아서 5솔을 달성했다. 

그러고 스코어보드를 보니 1분 전에 G 퍼솔을 먹고 5솔을 달성한 사람이 있더라.... 여전히 2등이어서 일단 C는 넘기고 G로 넘어갔다. 

 

 

[02:14] G 2 WA

 

또 멍청하게 페널티를 적립했다. 디버깅 코드를 지우지 않아서 출력 초과를 한 번 받았다.

그다음 다시 제출하니 WA를 또 받아서 많이 당황했다. 풀이에 틀린 점이 크게 없다고 생각했기 때문이다. 

 

 

[02:21] G solved

 

이 문제도 마찬가지로 문제를 딱 보면 세그트리 문제라는 걸 알 수 있다. 

다만 update 쿼리가 다루기 까다로웠다. 

특정 집에서 갈 수 있는 집의 최대 범위를 안다면 min query는 매우 간단한데, 이 최대 범위를 직접 계산한다면 쿼리마다 nlogn의 시간이 걸리게 된다. 

몇 분 생각해보니, 최대 범위를 찾아야 하므로 이분 탐색으로 가능하지 않을까 하는 생각이 들었고, 거리들을 또 다른 segtree에 넣어서 range sum을 이용하면 되겠다는 생각이 들었다.

시간 복잡도를 계산해보니 대충 쿼리마다 (logn)^2 정도가 나올 것 같아서 구현을 시작했다. 

두 번째 WA는 구현 실수가 있었다. 사실 실수를 정확히 찾았다기 보단, 이렇게 구현하면 틀릴 수도 있나? 반신반의한 상태로 살짝 바꿔서 다시 제출했는데 AC를 받아서 다행이었다. 

 

2시간 이후부터 스코어보드가 프리즈가 되었는데, 이 시점에서 6 솔브로 추정되는 사람들은 아무도 없어서 1등이 되었다. 

C와 H, I가 남아있었는데, H와 I 모두 유형은 파악이 됐다. 

H는 게임이론이었고, I는 플로우 문제였는데 사실 스프라그-그런디 정리에 대해서 완벽히 습득이 안된 상태였고, I는 그 뒤의 문제이므로 적어도 플1 ~ 다이아 정도는 되겠다 싶어 C로 넘어갔다. 

C만 해결하면 7솔브이고, 이 시점에서 스코어보드상으로 5솔 1명, 4솔 3명이어서 C만 풀면 무조건 1~2등이다 생각했다. 더군다나 앞문제이니 다시 풀면 금방 풀 수 있을 거라 생각했다. 

 

 

[02:35 ~ 03:38] C 12 WA

 

1시간 동안 아무것도 못했다. 엄청난 맞왜틀을 시전했다. 중간중간에 풀이도 몇 번 바꿔보고 코드도 새로 다시 짜보고 했는데 계속 WA가 나왔다. 손으로 만들어본 예시가 몇 개 인지도 모르겠다... 

인터랙티브 문제라 디버깅도 하기 힘들고 몇 번 WA를 받고 1시간쯤 남았을 때 스코어보드를 보니, C를 풀기만 하면 페널티 따위는 상관없겠다 싶어 분노의 제출을 했다. 그래도 여전히 풀리지 않았다 ㅠㅠ

위의 사진을 보면 알 수 있듯이 대부분 C를 다 풀었기에 더 이해가 안 되었고 결국 13 WA라는 엄청난 결과를 찍고 났을 땐 이미 20분밖에 남지 않았다...

 

(여담으로 C덕분에 가장 많은 WA를 받은 사람에게 주는 특별상을 받게 되었다. 애증의 문제...)

 

 

[03:59] H 1 WA

 

사실 예제도 제대로 나오지 않은 코드이다. 

시간이 다돼서 스코어보드 까는 재미를 위해 그냥 제출했다.

혹시나 스프라그 그런디 정리 문제가 아니라 단순히 DP를 이용한 게임 이론 문제인가 싶어서 구현을 했는데 역시나 예제도 잘 나오지 않았다. 

그냥 C에 매달리지 않고 H를 잡았으면 어떨까 생각도 잠깐 했지만, 그래도 C를 풀 확률이 더 높았을 것 같다. 

대회 전, 날짜가 얼마 남지 않은 상황에 게임 이론에 대해 공부해서 다른 문제를 풀어볼 기회가 없었는데 이 부분이 많이 아쉬웠다. 

 

---

결국 6 솔브로 2등을 차지했다. B와 C에서 많이 말려서 페널티를 많이 쌓기도 했지만, 또 처음에 C에서 계속 잡았다면 더 끔찍한 결과가 나왔을 것 같아 다행 반 아쉬움 반이다. 1등(wbcho0504)에 비해 객관적으로 조금 떨어진다고 생각해서 2등도 나쁘지 않은 것 같다.

특히, 열심히 준비를 해와서 그런지 크게 후회가 없는 점이 다행이다. 그렇지 않았다면 혼자 되게 스트레스를 받았을 것 같다.

장기간 PS를 해오다 보니, 이제는 뭔가 눈에 보이는 결과에 의해서 내가 스트레스를 받지 않는 게 더 중요한 것 같다.

쉽진 않겠지만 언제나 행복 PS를 꿈꾸고 있다 :)

 

이제 일주일 남은 2021 SUAPC winter 대회만 남아있다. 이미 '그 팀'이 나온다는 얘기를 듣고 1등의 꿈은 물 건너갔지만... 후회 없는 대회가 되었으면 좋겠다. 이 대회를 잘 마치고 나서 PS에 대한 노력은 조금 줄이고 얼른 다른 공부에 매진하고 싶다. 

[2021 SUAPC Winter] No Orange cant win팀 화이팅-!

 

겨울 캠프랑 대회를 잘 이끌어주신 신촌 연합 운영진분들 수고 많으셨습니다 :)