2022 ICPC Seoul Regional 후기

프리즈 기준 스코어보드 / 맨 위에서 찍을 수 있었으면 좋았을텐데

2022 ICPC Seoul Regional에 GreenBelt팀으로 출전하였다. 전체 12문제중 5문제를 해결하고 프리즈 기준 39위, 최종 43위를 달성했다. 피곤해서 좋은 글이 써지지 않는 것 같지만, 기억이 휘발되기 전에 대회 중에 있었던 일을 시간 순으로 복기해보고자 한다.

 

대회 시작 전에 풍선이 앞에 놓여있길래, 풍선의 개수를 세어서 난이도를 예측하려고 했다. 후에 들은 이야기로는 풍선 개수를 일부러 맞춰놓았다고 한다(...) 그냥 플라시보였음.

J. Parentheses Tree (AC at 10 min)

사실 그림이랑 예제입력보고 쫄았는데 문제를 읽자마자 별거 아니라는걸 깨달았다. 구현에는 그렇게 많은 시간이 걸리지 않았는데 10분에 AC를 받은 이유는, 키보드를 교체하고 자리까지 바꿨기 때문이다. 지금 생각해보면 굳이 그럴 필요가 없었다. 괜히 장비탓을 했던거같음... 스태프분들 죄송합니다.

F. Frog Jump (AC at 27 min)

I를 잡고 고민을 하다가 팀원이 아이디어를 알려줘서 바로 구현해서 맞았다. 아이디어를 듣고 보니 KOI 기출인 개구리 점프의 상위호환이었다. 구현할 때 누적합을 구했어야했는데 그러지 않아서 한번 틀린 후 맞았다.

K. Shuffle Game (AC at 79 min)

대회 초반에 모두가 I, J 순으로 풀때 우리만 J, F, K 순으로 해결했다. 그만큼 I에서 많이 막혀있었다. 여튼 I는 처음에 내가 잡고 고민을 하고 있었는데, 팀원에게 넘겨준 후 K를 풀었다. 좀 피상적으로 간단히 이야기 하자면 2대1로 매칭하는 버전의 LCS를 짜는 문제였다. DP 케이스 워크를 잘못해서 한번 틀린 후 맞았다.

I. Palindrome Type (AC at 117 min)

보자마자 BOJ17609 회문이 떠올랐다. 사실 저 문제처럼 그리디하게는 안되는 것 같아서 DP를 했다. 처음 DP는 틀렸었고, 뭔가 DP 테이블 정의를 팀원에게 던져줬더니, 팀원이 바로 풀어서 맞았다. 발상은 입력 문자열 S와 S의 reverse인 T에 대해서, S와 T의 LCS의 길이를 구하면 되는 것. 그런데 LCS의 길이가 N-3이상이어야하기 때문에 S에서 건너뛴 문자의 개수랑 T에서 건너뛴 문자의 개수를 관리해주면서 DP를 돌려주면 되었던 것 같다.

E. Forbidden Turns (AC at 208 min)

간선을 정점으로 생각하고 다익스트라를 쓰면 되는 문제인데, 구현에 말려서, 풀이를 설명해주고 팀원에게 넘겼다. 이것도 팀원이 잘 풀어서 맞았다.

 

이후에는 대회시간내에 풀지 못했지만 시도했던 문제들이다.

D. Folding Stick

진짜 할말이 많은 문제다. 문제를 보자마자 $D(i) = \min_{j \text{ s.t. } D(j) + S(j) \leq S(i)} (S(i) - S(j))$를 떠올리고, $(D(i) + S(i), S(i))$를 Dynamic Segment Tree로 관리해주면 되겠다고 생각했다. 그리고 바로 Dynamic Segment Tree를 팀노트에서 베껴썼는데... 로컬 실행 결과는 Segmentation Fault. 다이나믹세그를 잘 쓸줄 모르는 것 같다고 생각이 들어서, 바로 풀이의 방향을 전환했다. 결정문제 $f(x)$를, 각 접힌 segment들의 길이가 x이하가 되게 할 수 있는지로 정의했는데, 사실 안 될 것 같다는 느낌이 있었는데도 불구하고 코드를 짜고, 심지어 모든 예제가 돌아가고 반례도 찾을 수 없어서 왜 틀렸는지 한참동안 붙잡고 있었다. 사실 이렇게 끝났으면 별로 아쉽지 않았을 것 같은데, 다시 파라메트릭을 포기하고 dp 풀이로 돌아왔다. 두가지 다른 시도를 했었고, 지금 생각해보면 왜 그렇게 무식하게 생각했는지 잘 모르겠다. 처음에는 $D(j) + S(j)$가 증가한다고 생각해서 이분탐색을 썼는데, 당연히 저 수열이 증가할리가 없었다. 두번째는 i에 대해서 $D(j) + S(j) \leq S(i)$인 $j$가 단조증가하니까 투포인터로 찾으려고 했다. 그런데 조건을 만족하는 $j$를 모두 모아보면 항상 연속한 하나의 구간을 이루고 있다는 보장이 없었다. 대회가 끝나고 풀이가 왜 틀렸는지를 깨닫고 나니 힙을 이용하는 정해가 바로 떠올랐기에 더욱 아쉬운 문제인 것 같다.

L. Two Choreographies

내가 D를 잡고 씨름하는 동안 다른 팀원은 L을 잡고 씨름하고 있었다. 무슨 문제인지도 잘 몰랐는데, dfs tree를 만들고 거기서 관찰 몇개랑 예외 처리를 컨스트럭티브로 해주면(????) 되는 문제라고 들었다.

 

이번 대회는 왜인지 구현 실수가 너무 많았다. 예선때는 구현을 한 번만 하면 바로 답을 맞췄었는데, 본선은 그렇지 않았다. 문제가 더 어렵기 때문이거나 아니면 그동안 내가 ps를 거의 하지 않았던 탓일 것 같다. 그리고 확실히 팀원이 나에 비해서 차분하게 문제를 해결하고 구현을 했기에, 이건 내가 보고 반성하고 본받을 점이라고 생각한다... 마음이 급해지는게 만악의 근원이다. 여유 최고!

 

이전 대회는 성적은 좋았을지라도 내 실력이 모자라서 거의 실력자가 몰아주는 버스에 무임승차한것과 다름이 없었는데, 이번 icpc는 예선도 본선도 문제 해결에 많은 기여를 할 수 있어서 조금 더 즐거웠던 것 같다. 그리고 팀원들이 나의 부족한 점(구현... 케이스워크... 경우의 수...)을 잘 채워주었고 나도 그럴 수 있어서, 팀워크로는 여태 출전한 대회중에 제일 좋았던 것 같다!

 

작년 icpc와 비교하면 올해 실력이 정말 많이 늘었는데, 그래도 공부를 게을리 하지 말아야겠다는 동기부여가 되었다. 당장 저번주만해도 icpc 수상은 별로 생각이 없고, ps도 이정도면 앞으로 살아가고 취업하는데 문제 없을만큼은 하지 않았나 하는 생각이 있었다. 그런데 확실히 이런 큰 무대에서 문제를 많이 해결하고, 수상까지 하는 팀을 가까이서 보니까 욕심이 생기지 않을 수가 없는 것 같다. 대학은 한 학기에서 1년을 더 다니게 될 텐데 생각해보니 그 사이에 나갈 수 있는 대회도 굉장히 많아서, 좀 열심히 공부를 해서 내년에는 수상권을 노려보면 어떨까 하는 마음을 가졌다.

 

아자아자!!