2022 ICPC Seoul Regional 후기

2022 ICPC Seoul Regional에 HappyLastDance 팀으로 출전하였다. 팀원은 UCPC 2021/2022 팀이랑 동일하게 군대 선임 두 분(stabilizer_h, harinboy)이다.

인터넷 예선을 나름 성공적으로 쳤지만 아쉬운 부분도 분명 있었기에 열심히 연습을 하고자 했고, 다른 해야 할 일이 산더미지만 일단 유기하고(...) 리저널 전까지는 PS 연습에 집중하기로 했다. 그냥 여유 시간이 생기면 일단 PS를 했던 것 같다. 그렇게 문제를 열심히 풀면서 "피곤한 상태로 코딩을 하면 별 이상한 데서 실수를 한다" 라는 사실을 깨닫고, 전날에는 일찍 잤다. 그렇게 긴장된 채로 오늘(11월 19일) 대회를 치르게 되었다.

결과 및 후기

10솔브로 3등을 기록했다. (서울대 2등) 2등하고 페널티가 13분 차이인데, "딱 1번만 덜 틀렸으면" 하는 생각이 들지만 어차피 결과론이다. 그렇게 따지면 2등 팀도 1번 덜 틀렸으면 똑같은 거니까.. 그리고 중요한 것은 꺾이지 않는 마음 학교 내 순위는 바뀌지 않는다는 것이다.

이번 대회에서 이 팀으로 낼 수 있었던 거의 최상의 퍼포먼스를 냈다고 생각한다. 문제 푸는 속도도 그렇고, 운도 생각보다 더 잘 따라주었다. 그럼에도 1등 팀은 그냥 이길 수가 없었다. 체급 차이란 게 무엇인지 뼈저리게 느낄 수 있었다. 초반 9문제를 거의 쉼 없이 풀고 코딩하고 했는데도 스코어보드를 볼 때마다 1문제씩 뒤쳐져 있었으니.. 내가 못해서 졌으면 정말 슬펐을 것 같은데 이렇게 열심히 하고 나니 그래도 유종의 미를 잘 거둔 것 같다. 여담으로 이번에 3등을 기록함으로써 총 4번의 Seoul Regional에서 1, 2, 3, 4등을 모두 수집하는 데 성공했다.

그리고 안 그래도 복잡한 World Finals 대회 참가 팀 뽑는 규칙이 코로나 때문에 더 복잡해졌는데, 아무튼 결론부터 말하면 우리 팀이 월파에 갈 수도 있고 안 갈 수도 있다. (https://icpc.global/regionals/rules 참고) 2021, 2022 Seoul Regional에서 티켓을 딴 서울대 팀이 동일한 팀원 구성이기 때문에 이 팀은 2022/2023 WF 중 한 곳에만 출전할 수 있다. 그래서 나머지 하나의 WF에 나갈 팀을 2021/2022 서울대 2등 팀 중에서 하나 골라야 하는데 이것은 학교 coach를 통해 request해야 하고, detail은 나중에 알려준댄다. 아무튼 그래서 확정이 될 때까지 손가락 빨면서 기다려야 한다. 

대회 타임라인

대회장 앞을 보니 풍선이 12개가 있길래 문제가 12개인가 보다 했다. 여느 때와 같이 나는 ABCD를 읽었는데, 바로 풀 수 있는 게 안 보여서 약간 방황을 했다. 다행히 곧 정현이가 F를 풀어보라고 던져 주었다. F는 쉽게 풀 수 있는 문제였고, 짜서 내니 퍼솔이었다 (8min AC).

F를 짜는 중간에 스코어보드를 봤는데 J가 많이 풀리고 있길래 다음은 J를 해야겠구나 하고, J를 봤다. J는 구현이 매우 간단한 문제라서 빠르게 짜서 냈다. (11min AC).

그 다음에는 I가 풀렸길래 봤는데, 처음에 뭔가 쉬운 방법이 안 떠올라서 약간 헤맸다. 다행히 곧 모든 경우의 수를 다 해보는 것이 별로 안 걸린다는 것을 깨닫고 구현을 할 수 있었다. 사실 뭔가 edge case가 까다로울 것 같이 생겨서 틀릴 것을 각오하고 냈는데 한 번에 맞아서 다행이었다. (20min AC).

그 다음에 역시 풀린 K를 봤는데 그냥 simple DP였다. 구현은 적당히 빠르게 했는데 왠지 모르게 예제가 안 나와서 고치느라 시간을 약간 썼다. 변수명을 겹쳐 써서 그런 거였었다. 예제가 안 나올 정도의 오류라 다행이었다. 고치고 맞았다. (30min AC).

E가 풀렸길래 좀 봤는데, 뭔가 간선을 상태로 다익스트라를 하면 될 것 같은데 전이를 제곱 미만으로 줄이는 방법이 생각나지 않았다. 사실 22분에 풀렸을 때 뭔가 눈치를 챘어야 했는데 사실 푼 팀이 팀인지라.. 무슨 이상한 자료구조를 10분만에 짰을 수도 있다는 생각이 들어 마음만 계속 급해졌다. 그러다가 다행히 하린이가 D를 풀었다고 해서 컴퓨터를 주고 문제 풀이에 집중했다. 아마 이 때 C의 풀이를 대충 생각했던 것 같다. D는 한 번에 맞았다 (45min AC).

그리고 나서도 E를 아직도 모르겠어서 일단 L의 풀이(에 접근하는 과정)를 짜려고 했는데, 하린이가 지문을 읽더니 "outdegree <= 10" 조건을 찾아주었다. 예선 때는 하린이가 못 읽은 조건을 내가 찾아줬었는데 ㅋㅋ; 아무튼 그 조건이 있으면 그냥 특별한 자료구조 없이 단순히 짜면 되는 문제였기에 구현을 하였다. 시작점과 끝점이 같을 수 있다는 것을 한 번 간과한 덕에 페널티를 하나 먹었다. (58min AC +1).

그동안 정현이가 A의 풀이를 던져 주었다. 풀이의 핵심이 "cell의 좌표 홀짝성에 따라 독립적으로 나눌 수 있다" + "cell을 하나 골라 없애면 나머지 cell들이 subgame으로 잘 나뉜다" 인데, 내가 두 번째 사실이 성립하지 않는 줄로 알고 있었다. 심지어 코딩 하다가 중간에 물어보기까지 했는데 다행히 뒤집히려던 버스를 정현이가 바로잡아주었다. 코딩하는 것 자체는 그렇게 오래 걸리지 않았고, 짜서 내니까 한 번에 맞았다. 퍼솔! (77min AC)

그리고 나서는 풀이가 나와 있던 C를 드디어 코딩하기 시작했다. 뭔가 할 게 이것저것 많아서 구현이 생각보다는 조금 더 걸렸는데, 예제가 나오길래 내니까 TLE를 받았다..? 다시 코드를 보니 뭔가 vector를 잔뜩 떡칠해 놓았길래 그냥 다 전역 배열로 바꿨더니 AC가 나왔다. 맞아서 다행 ㅎ (108min AC +1)

이제 L의 풀이를 하린이와 함께 마무리하여 코딩을 하는데, 뭔가 내가 첫 단추를 BFS Tree로 잘못 꿰어서 그런지 (DFS Tree를 그리면 훨씬 깔끔한 풀이가 존재함) WA를 2번 받아가면서 덕지덕지 수정한 끝에 맞을 수 있었다. 마지막엔 lca까지 구함; (144min AC +2)

그리고 나서 남은 세 문제를 봤는데, 셋 다 상당히 노답이어 보였다. B는 분명히 선발고사에서 똑같은 문제를 본 적이 있는데 그 때 무려 0점을 받았기 때문에 + 풀이 설명은 다 까먹었기 때문에 아무런 도움이 안 되었다. n^2 dp라는 사실 하나는 기억해낼 수 있었다. 그리고 G랑 H 역시 전혀 모르겠었다. 그렇게 시간은 시간대로 가는데, 앞에서 다른 경쟁자 팀들은 하나씩 문제를 풀어내는 것 같아서 이 때 잠시 멘탈에 위기가 왔었다.

그렇게 한 1시간쯤 "대회 그냥 지금 끝내주면 좋겠다" 상태로 있다가 갑자기 H에서 뭔가 할 수 있겠다는 생각이 들었고, 시간복잡도를 증명할 수는 없지만 왠지 짜면 맞을 것 같다는 생각이 강하게 들어서 바로 짜서 냈다. 코딩은 생각보다 오래 걸리지 않았고 한 번 WA를 받긴 했지만 맞을 수 있었다. (259? min AC +1)

그리고 나서 G를 잠시 보다가 안 되겠다는 결론을 내리고, 정현이가 만들어 준 B 풀이를 구현하기로 했다. 굉장히 여러 부분에서 헷갈릴 곳이 많이 있었는데, 세 명이 같이 달라붙어서 코딩을 하니까 t=1에 해당하는 코드가 예제가 모두 나오는 기적을 볼 수 있었고, 제출을 할 수 있었다. 하지만 어김없이 WA. t=2에 해당하는 부분이 틀렸음을 발견하고 남은 5분 동안 최대한 고쳐 보았지만 역부족이었다.

중간에 정신을 너무 늦게 차린 점은 좀 아쉬운 점이지만, 그래도 초반 페이스가 매우 좋아서 만족할 만한 결과가 나온 듯 하다. 

문제별 풀이

A

https://www.acmicpc.net/problem/16883 똑같은 문제가 백준에 있었다고 한다.

https://www.acmicpc.net/problem/11717 유사한 문제 역시 백준에 있었고, 이건 나 포함 90명이나 풀었다 (ㅋㅋ)

여튼, 일단 i+j의 홀짝성에 따라 완전히 독립적인 두 게임으로 나눌 수 있으니 그렇게 나누고, 각각은 생각을 편하게 하기 위해 좌표를 45도 돌려서 생각하자. 이제, 직사각형 격자에 cell들이 있고 이들을 규칙에 따라 잘 지우면 되는데, 빈 칸이 있을 수도 있다. 그런데 생각을 해 보면 초기에 cell들이 존재하는 모양이 하나의 마름모 모양 덩어리이고, 임의의 cell을 선택해서 연결된 부분까지 따라서 쭉 지우고 나면 완전히 분리된 직사각형으로 subgame들을 나눌 수 있다.

이제 독립된 subgame들에 대해 승패를 어떻게 판정하는지 생각해 보면, Grundy number의 개념을 알고 있다면 간단히 구할 수 있다. dp[sx][sy][ex][ey]를 [sx, ex] x [sy, ey] 직사각형에 대한 Grundy number라고 정의하면, 가능한 모든 move를 하나씩 시도해 보면서 그 때 나누어지는 직사각형들의 Grundy number를 모두 xor한 값들을 다 구한 뒤 이들의 mex를 구하면 dp값을 재귀적으로 구할 수 있다. 처음에 i+j의 홀짝성에 따라 독립적인 게임으로 나누었으므로 각자 Grundy number를 구해서 XOR한 뒤 0이 아니면 선공 승('W'),  0이면 후공 승('L')을 출력하면 끝.

N, M이 25 이하로 매우 작기 때문에 대충 아무렇게나 짜면 O(N^3M^3)에 풀 수 있다.

B

https://arxiv.org/pdf/1606.06940.pdf

사실 풀이 자체는 (충분히 잘 하는 사람의 경우) 논문과 별개로 생각해 낼 수 있는 수준인 것 같긴 한데, 올바른 가정을 정확히 찾아서 O(n^2) DP로 처리할 수 있도록 formulation해야 함, 입력 parsing이 헷갈리는 부분이 많음, t=2인 케이스가 생각보다 더 처리할 게 많음 등등의 이유로 AC를 받는 것은 풀이를 생각하고 나서도 매우 험난한 과정으로 보인다.

참고로 이 문제와 동일한 문제가 2016년도 국제정보올림피아드 1차 선발고사에 출제된 바 있고, 약간 다른 버전 (bounding box의 넓이 최소화) 문제가 2019년도 국제정보올림피아드 2차 선발고사에 출제된 바 있다. 여러분도 꼭 기출 논문문제 공부를 열심히 하도록 하자.

C

사변형을 잘 세는 좋은 방법 중 하나는 "대각선을 고정하는 것"이다. 대각선을 고정하고 나머지 두 점을 잘 고르면 사변형을 만들 수 있는데, 우리가 세고 싶은 것은 내부에 포함하는 점이 없는 사변형이므로 직선의 양 쪽에서 "내부에 포함하는 점이 없는 삼각형"을 하나씩 고르면 될 것 같다.

이런 쌍들을 다 세면 우리는 답이 되는 각 볼록사각형에 대해 정확히 2번, 각 오목사각형에 대해 정확히 1번씩 고려를 하게 된다. 이렇게까지만 하면 아직 답을 알 수 없으므로, 오목사각형에 대해서만 따로 한 번 더 세주면 좋을 것 같다. 왜 오목사각형에 대해 1번 덜 세게 되는지에 대해 생각하면 방법을 고안할 수 있는데, 바로 같은 쪽에 있는 서로 포함관계에 있는 삼각형을 고려하는 것이다.

"포함관계"를 잘 나타내기 위해 대각선을 이루는 두 점 (A, B)를 각각 기준으로 하여 ccw 순서대로 인덱스를 매기자. 이제 각 점을 새로운 2차원 좌표계 (원래 x,y 좌표계가 아닌 인덱스 i,j 좌표계) 에서 나타냈을 때 포함 관계에 있는 점을 각 인덱스의 대소 관계로 나타낼 수 있다.

이제 우리가 세려는 두 가지 케이스는 위에서 정의한 인덱스 좌표계에서 효율적으로 처리할 수 있다.

볼록사각형 2개 / 오목사각형 1개 케이스 : 선분 양쪽의 부분에 대해 "0개의 점을 포함하는 점"의 개수를 Fenwick Tree를 활용한 sweeping으로 대각선 하나당 O(NlogN), 총 O(N^3logN)에 셀 수 있다. 각각 세서 곱한 값을 다 더하면 된다.

오목사각형에 대한 나머지 대각선 케이스 : 임의의 k에 대해 "k개의 점을 포함하는 점 P", "k개의 점 + P를 포함하는 점 Q"의 두 점 쌍으로 나타낼 수 있다. 역시 Fenwick Tree를 적절히 사용하여 plane sweeping을 해 주면 총 O(N^3logN)에 구할 수 있고, 시간이 너무 오래 걸리지 않도록 유의하여 구현하면 AC를 받기에 충분하다. 관찰을 조금 더 하면 O(N^3)도 된다는데 나는 잘 모르겠다.

D

(11.21 : 내가 안 풀어서 몰랐는데, 백준에 올라왔길래 풀고 추가)

힌지를 왼쪽에서부터 하나씩 접어야 하니, 자연스럽게 아래와 같은 꼴의 DP를 생각할 수 있다.

dp[i] : i번째 힌지를 마지막으로 접었을 때 위쪽으로 튀어나온 최소 길이

편의상 스틱의 맨 왼쪽/오른쪽에 가상의 0/n번 힌지가 있다고 하고, 각 힌지의 상대적인 x축 위치를 x[i]라고 정의하자. (x[0]=0 < x[1] < x[2] < ... < x[n]) dp 배열을 다 계산했다 치면, 답은 min(max(dp[i], x[n] - x[i]))가 된다.

dp 식은 다음과 같다 : dp[i] = min(x[i] - x[j]) for x[j]+dp[j] <= x[i].

dp[j]를 구하고 나면 x[j]가 그 뒤의 dp 값에 기여할 수 있는 순간은 x[j]+d[j]가 x[i] 이하가 되는 순간부터이다. x[i]가 i에 대해 증가하므로, priority_queue 등의 자료구조를 사용하여 각 j에 대해 x[j]를 고려해야 하는 최소의 i를 효율적으로 구하면 문제를 O(nlogn)에 풀 수 있다.

E

forbidden turn은 "특정 2개의 edge 순서쌍을 연속으로 사용하면 안 된다" 로 해석할 수 있다. edge를 정점으로 생각하여 dijkstra를 진행하면 정점의 개수를 O(E)로 바운드할 수 있다. 문제는 edge->edge 전이의 개수가 최대 O(E^2)까지 늘어날 수 있다는 것인데, 문제 지문을 잘 읽어 보면 "각 정점의 outdegree가 10 이하다" 라는 조건이 숨겨져 있어서 그냥 무지성으로 짜면 시간 안에 나온다. 상당히 마음에 안 드는 스타일인데 seoul regional에 유독 자주 나오는 형태(이상한 제약조건 걸어서 문제 억지로 풀리게 만드는 것)이니 유념하면 좋다.

F

서로 붙어있는 구간들은 하나의 컴포넌트가 되므로 큰 구간 하나로 합쳤다고 생각해도 된다. 이제 모든 구간은 disjoint하고, 수직선 상에서 인접한 두 구간 사이의 거리가 뛰어넘는 cost가 된다. 그냥 각 구간의 길이를 0으로 줄이고 간격만 그대로 유지했다고 생각해도 문제 상황이 똑같으니, 그냥 각 컴포넌트마다 x축 상의 위치를 정해버릴 수 있다. 이제 k개의 구간을 순서대로 방문하는 것은 인접한 두 구간 번호에 해당하는 x좌표의 차이를 다 더해주면 끝이다.

G

어케품

H

우선 "정확히 k번 등장하는 문자열"들을 어떻게 효율적으로 탐색할지 생각해 보자. 일단 Suffix array와 lcp array를 그려 놓고 생각을 해 보면, 아래 그림처럼 lcp 값을 기준으로 Suffix array 상의 suffix들을 적절한 block들로 나눌 수 있다.

각 block의 의미는 해당 block 내의 (l <= i <= r) 각 sfx[i]에서 시작하는 길이 [s, e]인 substring이 모두 정확히 k=r-l+1번 등장하는 substring이라는 것이다. leaf node가 최대 n개인 tree 구조이므로 block의 총 개수는 2n-1개 이하이다.

이제 해당 block에서 d(T)의 최댓값 및 그런 d(T)를 가지는 가장 긴 substring의 길이를 구하자. 문자열의 길이 a를 정하면 block의 각 sfx[i]를 저장하는 set 자료구조가 있다고 할 때 가장 작은 sfx[i]부터 시작하여 매번 (마지막 등장 위치)+a 이상인 최소의 sfx[i] 값을 찾는 것 (set에 lower_bound 함수가 있다) 을 반복하는 그리디 전략으로 해당 길이에 대한 d(T)를 구할 수 있다.

우선 블록 내에서 d(T)의 최댓값은 길이가 s인 substring의 d(T) 값임이 분명하다. 그리고 d(T)가 그 최댓값과 같은 최대 substring의 길이는 [s, e] 범위의 이분 탐색을 수행하면 구할 수 있다. 위에서 말한 "d(T) 구해주는 함수"를 블록당 O(log(n))번 호출하게 된다. 이제 등장 횟수 k에 대한 답을 갱신해주면 된다.

set 자료구조를 만드는 걸 naive하게 하면 그게 O(n^2)이라 시간초과가 날 수 있다. 이는 block이 트리 구조로 만들어진다는 사실을 이용하여, small-to-large 테크닉으로 각 block에 해당하는 set을 구축해주면 된다.

사실 시간복잡도가 왜 bound되는지 잘 모르겠다. 일단 대충 생각을 해 보면 길이가 a인 정확히 k번 등장하는 substring의 d(T)를 구할 때 O(min(n/a, k)*log(k)) 시간이 걸리고, a가 작으면서 k가 큰 경우가 그렇게 많이 없기 때문에 오래 걸리지 않을 것이라는 짐작은 할 수 있다. 그렇게 대충 믿고 제출을 하면 맞기 때문에 풀 수 있었던 것 같다.

I

문자열의 맨 바깥쪽 양 옆부터 서로 다른 문자가 나올 때까지 쭉쭉쭉 매칭시켜주면서 들어오자. 만약 두 문자가 다른 위치를 발견했다면, 해당 위치의 두 문자 중 하나는 무조건 빼야 한다. 왼쪽을 빼거나 오른쪽을 빼거나 둘 중 하나므로 각 경우에 대해 재귀 호출 등을 통해 모두 시도해 보자. 최대 3개의 글자까지만 빼 보면 되므로 재귀 호출은 많아야 2^3번 일어나고, 각 호출 내에서는 O(n)번의 연산이 이루어지므로 시간 복잡도가 O(n)이 된다.

J

문자열의 앞에서부터 보면서 '('가 나오면 depth가 1 증가하고, ')'가 나오면 depth가 1 감소한다. 또한, 트리의 정의를 잘 살펴 보면 "()", 즉 여는 괄호 바로 뒤에 닫는 괄호가 있으면 거기가 리프라는 사실을 알 수 있다. 다른 모든 곳은 리프가 아니다. 이제 각 리프 노드에 대해 depth의 합을 구하면 된다.

K

dp[i][j][k] : X[1..i], P1[1..j], P2[1..k]로 얻을 수 있는 가장 큰 점수로 정의하면 LCS와 매우 유사한 DP 전개를 통해 답을 구할 수 있다.

L

우선 connected 가정이 없음에 유의해야 한다. 문제 조건에 따르면 무조건 정점이 m>=4개 있고 간선이 2m-3개 이상 있는 컴포넌트를 찾을 수 있으니 거기서 문제를 푼다고 가정하면 컴포넌트가 하나라고 가정해도 좋다.

DFS Tree를 그리자. 간선이 2n-3개 있으므로 Tree edge가 n-1개 있고 Back edge는 n-2개 있다. Back edge는 조상-후손 관계의 두 노드를 잇기 때문에 Tree 상의 depth 차이를 구해 보면 2 이상 n-1 이하이다. 여기서 만약 이 값이 같은 서로 다른 back edge를 찾으면 답을 찾은 것이다. (후손->조상까지 타고 올라간 뒤 back edge를 타면 cycle이 됨)

만약 값이 같은 게 없으면 이는 depth 차이가 2인 것, 3인 것, ..., (n-1)인 것이 각각 하나씩 있다는 뜻이다. (n-1)인 것이 있으려면 DFS Tree가 일단 일자로 쭉 있어야 한다는 뜻이다. depth 차이가 2인 back edge로 길이 3 사이클 하나가 나오고 depth 차이가 (n-1), (n-2)인 back edge 역시 길이 3 사이클을 무조건 만들 수 있음을 알 수 있다. 따라서 그 두 개를 출력하면 된다.

우리 팀은 BFS Tree를 그리는 이상한 풀이로 풀었는데 사실 아래의 이유(*)로 진짜 맞는 건지도 잘 모르겠고 좀 별로라 그냥 더 깔끔한 풀이로 소개한다.

(*) 역시나 이번에도(..) 데이터가 약해서 그냥 서로 다른 길이 3 사이클 2개 나올때까지 찾는 코드 같은 게 미러에서 통과되었다는 소문이 있다. (심지어 길이 3 사이클 없는 데이터를 만들 수 있음) 으휴..