ICPC Seoul Regional 2022 미러

올해에는 미러 콘테스트라고, 같은 문제 셋과 시간으로 누구나 참가할 수 있는 대회를 같이 열었습니다. 이미 ICPC를 졸업한 저는 미러에서 놀아보기로 했고, 전날 급하게 팀원을 구해봤지만 아무도 오지 않아서 혼자 풀었습니다.

그 대신 제가 사용하는 라이브러리 코드 복붙 가능 + 인터넷 사용 가능이라는 조건을 걸기로 했습니다.

타임라인

I 3분 AC

뒤에서부터 읽어보기로 했습니다. I가 짧길래 보니까 가장 긴 팰린드롬 부분수열의 길이를 구하면 풀리는 문제입니다.

S의 가장 긴 팰린드롬 부분수열의 길이는 S와 S를 뒤집은 문자열의 LCS의 길이와 같습니다. 그걸로 앳코더 옐로를 찍었기 때문에 강렬하게 기억에 남습니다. I번은 답이 일정한 범위 내에 없으면 -1을 출력하는 거라서 선형 시간에 풀 수 있지만, 귀찮아서 비트셋 LCS를 복붙하고 퍼솔했습니다.

K 18분 AC

그 후로 앞으로 쭉 넘겨 봤지만 다 길거나 어려워 보여서 다시 맨 뒤로 돌아와서 하나씩 읽어봤습니다. L은 생각이 많이 필요할 것 같았고, K는 보자마자 LCS 스타일의 dp인 것 같아서 풀었습니다. 얘도 퍼솔했습니다.

J 21분 AC

스코어보드를 봤더니 J가 많이 풀려있길래 풀었습니다.

F 35분 AC

스코어보드를 봤더니 F가 많이 풀려있길래 풀었습니다. KOI 개구리 점프 문제와 비슷하다는 생각이 들었습니다.

E 59분 AC

스코어보드를 봤더니 E가 풀려있길래 풀었습니다. 이걸 이 제한에 어떻게 풀지? 하면서 지문을 자세히 읽어봤는데 outdegree가 10 이하라는 조건이 숨어있어서 실망했습니다. 시작점과 도착점이 같을 때를 고려하지 않아서 한 번 틀렸습니다.

A 124분 AC

남은 문제들을 봤는데 BGH는 딱 봐도 어려울 것 같았고, C는 대각선 하나를 잡고 "빈 삼각형의 개수"를 세주면 되는 걸 알아냈지만 그 방법이 잘 떠오르지 않았습니다. 그래서 남은 것은 ADL. 먼저 A를 봤는데 BOJ 16883과 완전히 동일한 문제였습니다. 이렇게 같을 수가 있나...? 아무튼 그래서 풀이는 이미 알고 있었지만, 아쉽게도 저는 BOJ 16883을 푼 적이 없었습니다. 열심히 구현해서 BOJ 16883을 먼저 맞은 다음 (...) 이것도 맞았습니다. 45도 돌린 후에 시작 보드를 찾느라 매우 애먹었고 R과 B를 헷갈려서 한 번 틀렸습니다.

D 171분 AC

이쯤에서 D가 꽤 많이 풀려 있었습니다. dp식을 세우고 정리해 봤더니 prefix minimum 쿼리가 나왔습니다. 그런데 좌표 범위가 매우 큰 데다가 미리 받아서 압축할 수도 없었기 때문에, 진짜 이렇게 푸는 게 맞나? 생각하면서 dynamic segment tree를 짰습니다. 시간 제한이 무려 0.4초라서 두 번의 TLE 끝에 컷팅을 좀 해서 맞았습니다.

나중에 솔브드 디코에서 얘기해 봤는데 우선순위 큐로 풀린다고 합니다.

L 213분 AC

이쯤에서 L이 꽤 많이 풀려 있었습니다. 간선이 2n-3개 이상이라는 조건이 꽤나 의미심장합니다. 이 개수면 트리를 만들고도 간선이 n-2개나 남습니다. 근데 트리도 간선이 n-1개입니다. 이게 우연은 아닐 거라고 생각해서 이쪽으로 생각을 더 해봤습니다.

그 남는 간선들은 트리의 두 정점을 이으니까 그 간선들의 "거리"를 생각할 수 있습니다. 거리가 같은 두 간선이 있으면 걔네들을 가지고 길이가 같은 두 사이클을 만들 수 있습니다. 근데 거리는 2, 3, ..., n-1이니까 대부분의 경우에서 거리가 같은 두 간선이 존재합니다. 그 경우를 처리하고 절묘하게 2, ..., n-1이 하나씩 나오는 경우도 추가로 푼 다음 dfs 트리로 구현했습니다.

틀리고 보니 연결 그래프라는 가정이 없었어서 모든 연결 요소에서 한 번씩 저 풀이를 돌려서 맞았습니다. 이것 때문에 틀리거나 아쉽게 못 푼 팀이 많을 것 같습니다.

남은 1시간 동안에는 C의 풀이를 완성해서 구현했지만 예제 3도 정답이 나오지 않았습니다.

후기

풀이

https://kdh9949.tistory.com/45

체감 난이도

A Platinum 1
B ??
C Diamond 5
D Platinum 3
E Gold 2
F Gold 2
G ?? 
H ?? 아마 다이아 2-3 될 듯
I Gold 5
J Silver 1
K Gold 4
L Platinum 3