2024 KAIST 14th ICPC Mock Competition 문제 출제 후기

조금 늦었지만 이번 카이스트 가을대회에 출제한 문제들의 비하인드를 이야기해보자 한다.

 

1. Same segment

원래 골드 문제를 위한 문제였다. 가볍게 풀 수 있는 문제를 생각하기 위해서 익숙한 토픽들을 여러 개 훑는 중에 "주어진 구간 몇 개의 합이 자연수 K로 같은 음이 아닌 정수의 수열"이라는 토픽이 떠올랐다. 포함관계에 있는 구간이 없으면 그리디하게 앞에서부터 K/0을 채우면 되고, 포함관계에 있는 구간이 존재한다면 두 구간의 차집합에 0을 채우면 되는 아주 쉬운 문제였다. K가 답에 영향을 미치지 않는다는 아이디어도 괜찮아서 다항시간 풀이를 떠올리면 문제를 풀 수 있도록 N<=500으로 해서 낼 생각이었다. 

 

이 문제를 발전시키기 위해 포함관계에 있는 두 구간의 차집합에 0을 채우는 과정을 더 빠르게 할 수 없을까 생각했지만, 별 생각이 떠오르지 않았다. 그러다 문득 아주 간단한 dp 형태의 접근이 되지 않을까 생각하게 되었고, K=1인 경우에 O(NlogN)의 dp 풀이가 있다는 것을 발견하고 출제하게 되었다.

 

이 문제를 풀기 위해서 큰 노력을 들이지는 않았지만, 오랜 기간 가끔씩 고민해주었기 때문에 난이도가 가늠이 되지 않았다. 본 대회에서는 두 구간의 차집합에 0을 채우는 아이디어가 주로 풀이로 나왔고, 이는 구현이 복잡해서 모두 WA를 내놓았다. 문제를 음수 가중치가 있는 그래프에서의 최단경로 문제로 변형해서 푸는 뚫는 풀이도 몇 개 나왔다. 막지 못한 것이 아쉽다. 아무도 간단 심플 dp 풀이를 찾지 못해서 아쉬웠다.

2. Counting regions

고등학생 때 이러한 문제를 만든 적이 있다.

 

"N*N 격자 위에 행/열의 색을 검은색/흰색으로 칠하는 시행을 여러 번 한 후에, 왼쪽 위 칸에서 오른쪽 아래 칸으로 가는 경로 중 경로 위에 있는 칸의 색의 변화의 최솟값을 구하라"

 

하지만 이 문제는 너무 어려워서 풀이를 못 내고 죽은 상태로 있었다. 2024년에 다시 꺼내서 문제를 곰곰히 생각해보았는데, 내가 푼 이 문제가 루비 5이고 만든 문제는 해당 문제의 (거의)상위호환이기 때문에 풀 수 없다고 결론을 내렸다. 나름 아이디어가 좋다고 생각했던 나는 문제를 살리기 위해 몇 가지 변화를 시도한다. 경로라는 토픽에서 컴포넌트 개수라는 토픽으로 바꿨고, 행과 열을 순차적으로 칠하도록 조건을 추가했다. 

 

고등학생 때 이 문제를 푼 적이 있다. 컴포넌트의 개수를 세는 대신 컴포넌트와 일대일 대응하는 것(저 문제의 경우 구간의 왼쪽 끝)을 세는 아이디어가 재미있었다. 그래서 이 문제를 조금 변형해서 트리가 주어지고, 모든 간선 집합의 subset에 대해서 component 개수를 세는 것을 문제로 냈다. 지금 생각해보면 컴포넌트의 개수는 (정점 개수 - 간선 개수) 이기에 의미 없는 문제였지만 각 컴포넌트의 가장 위에 있는 노드를 기준으로 컴포넌트 개수를 세는 풀이를 만들었다. ucpc에 call for task를 하고 떨어졌다.

 

컴포넌트 개수를 셀 때 이 아이디어를 사용하면 예쁜 관찰을 할 수 있다고 생각했다. 각 시행에 의해 칠한 칸을 영역이라고 부르면, 아래쪽 인접한 영역, 오른쪽 인접한 영역과 색이 다른 영역의 개수를 세주면 된다는 것을 깨달았다. 이 관찰을 사용하면 충분히 문제를 만들 수 있다고 생각했다.

 

Help yourself처럼 모든 가능한 시행의 가짓수에 대해서 컴포넌트의 개수를 세는 문제를 만들고 싶었지만, 간단 심플 dp를 사용해서 문제가 풀리는 것이 마음에 들지 않았다. 몇 개 시행의 색을 고정하고, 나머지 색을 적당히 선택해서 컴포넌트의 개수를 최소화하는 문제를 만들고 싶었지만, 풀리지 않았다. (지금은 풀 수 있다) 그래서 최종적으로 하나의 시행의 색을 바꾸는 점 쿼리 문제를 내서 각 영역에 대해 아래쪽 인접한 영역, 오른쪽 인접한 영역과의 색의 차이를 세그먼트 트리로 관리하는 자료구조 문제로 만들었다. 괜찮은 문제라고 생각하고 만족하고 있었다.

 

안 좋은 소식이 좀 있었다. 일단 자료구조 구현이 생각보다 조금 복잡했다. 5000B 정도 되었는데, 팀대회에 이 정도 길이의 코드를 짜는 것은 버거울 것이라고 생각했다. 그리고 본 대회때 사람들이 관찰을 안 하고, 깡자료구조로 푸는 것에 대한 걱정도 생겼다.

 

색을 바꾸는 영역과 인접한 영역들이 선형으로 연결되어 있어, 이를 자료구조로 관리해주면 풀릴 것 같다고 예상을 했다. 조금 더 파고 들어가니까 자료구조 필요 없이 인접한 영역들 중 양 끝 영역의 색만 알고 있으면 컴포넌트 개수 변화가 -1~1 사이로 결정된다는 것을 깨달았다. 이러한 놀라운 결과의 근원지가 어디인지 알아내기 위해 컴포넌트의 구조를 살펴본 결과, 트리의 형태를 이루고 있어서 컴포넌트 개수의 관리가 아주 쉽게 상수 시간에 된다는 것을 깨달았다. 그래서 점 변경 쿼리 대신에 구간 변경 쿼리를 줘서 아예 자료구조 풀이를 막아버리고 컴포넌트 구조에 대한 관찰을 해야 풀 수 있게 했다.

 

검수를 받은 결과, 자료구조로 풀 수 있음이 밝혀졌다. 내가 컴포넌트 구조에 대해서 한 관찰이 필요 없어서 조금 아쉬웠다. 내 풀이가 선형이기 때문에 이러한 자료구조 풀이를 막을까 생각했는데, N과 NlogN는 구분하는 것은 세터, 검수자, 참가자들의 정신건강에 좋지 않다는 것을 One Two Three를 출제하면서 깨달았기 때문에 널널하게 NlogN이 돌도록 세팅했다. 결정적으로 구사과님의 검수 코드가 빠른 NlogN이었기 때문에 NlogN을 자르지 않았다.

 

이 문제도 굉장히 오랜 시간에 걸쳐서 조금씩 관찰을 해나간 경우이기 때문에, 난이도 예측이 안 되었다. D2 정도면 적당하다고 생각한다. 참가자들이 아무도 풀지 못했다.

3. Hexagonal tiling

이 문제의 시작은 LGV Lemma 렉쳐노트에 있다. 여러 ps 토픽을 공부하던 중, LGV Lemma도 공부하게 되었다. 해당 렉쳐노트에는 plane partition formula에 대한 풀이가 적혀있었다. 3차원의 쌓기나무를 육각형 판 위에서의 마름모로 변환을 한 뒤에, 여러 개의 겹치지 않는 path로 표현해서 LGV Lemma를 적용하는 문제이다. 아래는 대략적인 그림 설명이다.

plane partition이 쌓기나무로 변환된 뒤에 삼각격자 위에서의 겹치지 않는 여러 개의 path로 변환된다.

 

처음에 이 문제를 봤을 때는 단순히 재미있는 문제라고 생각하고 넘겼다. 그러다 문득 각 육각형 안에는 0도, 120도, 240도 돌린 마름모들이 존재하는데 각 종류의 마름모의 개수가 모든 타일링에 대해서 같은 것에 대해 의문이 생겼다. 혼자서 힘들게 풀고 있는데, 이 문제의 풀이에 해답이 있다는 것을 깨달았다. 육각형을 수평선으로 잘라서 각 수평선 위의 점들을 정점으로 해서 마름모 모양대로 path를 만들어주면 아주 쉽게 풀리는 것이었다. 이때 이 아이디어가 아주 대단한 아이디어라는 것을 깨달았고, 이것을 사용해서 플로우 문제를 만들자고 결심했다.

 

처음에는 정육각형 위에서 푸는 문제가 아니라, 한 변의 길이가 10 미만인 길쭉한 육각형 위에서 풀도록 대략적인 틀을 만들었다. 단순히 각 삼각형을 짝짓는 이분매칭의 풀이가 통과하면 안 되는데, 내가 플로우에 대해 잘 알지 못해 제한을 빡세게 잡은 것이었다. 이분매칭 풀이는 육각형 내부 삼각형 개수에 시간복잡도가 의존하지만 정해는 플로우의 크기에 비례하기 때문에 이러한 제한이 안전하다고 생각했다.

 

구사과님의 문제들 중에 플로우를 사용하는 문제가 꽤 많다. (스포 주의)이 문제가 그러한데, 플로우처럼 생기지 않은 문제에서 플로우를 적용하는 것이 아주 감동적인 문제이다. 나는 저 문제의 풀이를 봤고, potential이라는 개념을 사용하면 mcmf에서 플로우를 한 번 돌릴 때마다(최단경로를 찾을 때마다) O(|E|log|V|)의 시간을 사용할 수 있다는 것을 알고 있었다. 이를 사용하면 주어진 육각형이 길이 N의 정육각형일 때 만든 문제를 O(N^3logN)에 풀 수 있고, 이분매칭의 모델링에서는 적어도 O(N^4)의 시간은 필요할 것이라고 생각했다. 플로우를 O(N^2)번은 돌려야 하는데, 정점의 개수가 O(N^2)개이기 때문에 나름 타당한 추론이었다. 그래서 한 변의 길이가 10 미만이라는 제한을 제거하고 문제를 세팅했다.

 

플로우 문제의 세팅이 의외로 쉽게 끝났다. 이분매칭은 랜덤 데이터를 만들면 적당히 안 뚫렸다. 그래서 나는 방심하고 있었다. silverwolf가 yosupo judge에서 simplex network flow를 가져오기 전까지는 말이다.

비상~

 

Simplex network flow의 시간복잡도는 O(N^6)이지만, 저격데이터가 별로 없는 알고리즘의 특성상 main correct solution과 비슷한 시간에 돌았다. 처음 세팅에서는 플로우를 int를 사용해서 돌려도 괜찮게 각 마름모의 가중치인 w의 범위는 친절하게 100 이하였지만, 문제가 심플렉스 딸깍으로 터질 초초비상 상황에서 simplex의 시간복잡도에 logw가 들어가는 것을 보고 w의 제한을 10^9으로 늘렸다. 그리고 무엇을 의미하는지 모르겠는 제너레이터를 마구마구 추가하고 특수한 그래프에 대한 제너레이터를 몇 개 만들어서 돌려본 결과, simplex가 잘 막혔다. 여기에서 끝난 줄 알았는데, 약간의 최적화를 더한 코드가 모든 데이터를 뚫었다.

비상 22

 

이번에는 좀 머리를 써서 저격데이터를 완성했다. 뚝딱 저격한 것처럼 보여도 최적화된 심플렉스 풀이를 저격하는데 이틀 정도 걸렸다.

simplex 코드를 모두 저격했다!

simplexkillGen이 모든 simplex 풀이를 막는다. 아주 뿌듯했다

 

플로우 문제 세팅하는 것은 정말 쉽지 않다는 것을 깨달았다. 앞으로는 플로우 문제를 안 낼까 생각중이다.

 

본 대회에서는 많은 팀들이 이분매칭 풀이를 냈다. 모두 TLE났다. 지나가면서 참가자들의 종이를 관찰한 결과 한 팀에서 올바른 모델링까지 접근했지만 potential을 사용한 mcmf를 몰라서 못 풀었다는 것을 알아냈다. 참으로 안타까운 일이다.

4. 마무리

이번에 가을대회에 문제를 내면서 너무 즐거웠다. 비록 Counting regions와 Hexagonal tiling은 아무도 못 풀어서 아쉬웠지만, 나의 문제들이 세상에 공개되어 미래에 KAIST 대회를 미는 사람들이 나의 문제도 함께 풀어준다면 기쁠 것 같다. 앞으로도 대학 대회들에 재미있는 문제들을 많이많이 내야겠다.