2024 KAIST 14th ICPC Mock Competition 풀이

A. Automata Embedding

1. $f(i+1) \leq f(i)+1$

이는 kmp failure function의 특징 중 하나이다. $S[1...f(i+1)] = S[i+1-f(i+1)+1...i+1]$이라면 $S[1 ... f(i+1)-1] = S[i+1-f(i+1)+1 ... i]$이기 때문이다.

 

2. $f(i)$와 $i$를 잇는 화살표들을 평면 위에 그릴 수 있다는 것과 동치인 것은, 구간 $[f(i), i]$들을 정점으로 하고 두 구간이 겹치지만 포함관계에 없는 경우 간선으로 이은 그래프가 이분그래프인 것이다.

pf) 각 화살표를 위에 그리면 그룹 1, 아래에 그리면 그룹 2라고 하자. 같은 그룹에 있는 화살표들은 겹치면 안 되고, 이는 구간으로 만들어진 그래프에서 두 구간이 겹치지만 포함관계에 없는 것과 동일하다.

앞으로 '$f(i)$와 $i$를 잇는 화살표들을 평면 위에 그릴 수 있는 문자열'을 좋은 문자열이라고 하자.

 

3. $S$가 좋은 문자열이라고 가정하자. 어떤 $i$에 대해서 $f(i) \leq i-3$이라면 $j>i$에 대해서 $f(j) \leq i-2$이다.

pf) 어떤 $j>i$에 대해 $f(j) > i-2$라고 가정하자. 관찰 1에 의해서 $i < k < j$인 $k$가 존재해서 $f(k)=i-2$이다. $[f(i), i], [f(k), k], [f(j), j]$는 구간으로 만들어진 그래프 위에서 길이 3의 odd cycle을 만들기 때문에 관찰 2에 의해서 모순이다.

$i=1, 2, \cdots, n$까지 보면서 $S[1..i]$의 상태를 automata로 추적할 것이다. 이는 3가지 케이스로 나눌 수 있다.

 

1. $S[1..2]=aa$

$S$의 prefix에 대한 automata는 다음과 같이 나타난다.

xa는 a가 아닌 문자를 의미한다. 동그라미가 2개인 노드들은 $f(j)=0$인 $j \leq i$가 존재한다는 것이다.

 

2. $S[1..3]=aba$

$S$의 prefix에 대한 automata는 다음과 같다.

 

3. $S[1..3]=abb$ 혹은 $S[1..3]=abc$

$S$의 prefix에 대한 automata는 다음과 같다.

 

각 케이스에 대해서 automata를 인접행렬로 표현해서 거듭제곱 해주면 된다. 분할정복을 사용하면 $O(logn)$에 풀 수 있다.

B. Construct a Coin Set

$1, n, 2n-2$는 $N=2n$에서 반례이다. ($n \geq 3$)

$1, n, n+1, 2n-1$은 $N=2n+1$에서 반례이다. ($n \geq 3$)

$N \leq 5$에 대해서는 직접 모든 경우를 확인해서 불가능함을 보이자.

C. Counting Regions

Operation들을 역순으로 보자. Operation은 각 행/열에 아직 칠해지지 않은 칸을 칠하는 것으로 간주할 수 있다. 앞으로 서술할 때에는 operation들은 역순으로 보는 것으로 하자. 

각 operation에 대해서 칠하는 cell들의 집합을 영역이라고 하자.

 

Operation 실행 도중에 안 칠해진 cell들은 (1, 1)을 포함하는 직사각형으로 나타난다. 따라서 각 operation의 영역은 한쪽 변의 길이가 $1$이고 윗변/왼쪽 변이 정사각형 끝에 붙어있는 직사각형의 형태로 나타난다. $i$번 행에 대한 operation의 영역을 $S_{i, 1}$, $i$번 열에 대한 operation의 영역을 $S_{i, 2}$라고 하자.

$S_{i, j}$들의 인접 여부를 보존하면서 $2 \times (2N-1)$ 직사각형 내부에 새로운 영역 $S'_{i, j}$를 만들 수 있다는 것을 보이자.  이는 $S_{i_1, j_1}$과 $S_{i_2, j_2}$의 인접 여부가 $S'_{i_1, j_1}$과 $S'_{i_2, j_2}$의 인접 여부와 같도록 $S'_{i, j}$를 정할 수 있다는 것이다.

 

앞에서 설명했듯이 operation을 실행하는 도중에 안 칠해진 cell들은 (1, 1)을 포함하는 직사각형으로 나타난다. 직사각형의 둘레에는 인접한 영역이 $2$개 있다. $i$번째 operation까지 시행했을 때 $x_i$번째 행, $y_i$번째 열까지 칠했다면 $S_{x_i, 1}$과 $S_{y_i, 2}$가 둘레와 인접해 있다. 실행되는 operation의 영역은 이 두 영역과 인접한다. 이를 통해 각 영역에 대해 인접한 영역 중 자신보다 먼저 시행된 operation에 의한 영역은 최대 2개임을 알 수 있다.

 

$1 \leq i \leq 2N-2$인 $i$에 대해서 $(i, 1)$은 $S'_{x_i, 1}$, $(i, 2)$는 $S'_{y_i, 1}$에 속하도록 영역들을 배정하자. 이렇게 영역들을 나누면 각 영역들의 인접 여부를 보존할 수 있다. 마지막으로 기존 grid에서 $(1, 1)$은 $S_{2N-2, 1}, S_{2N-2, 2}$와 인접하니 $(2N-1, 1)$과 $(2N-1, 2)$와 대응시키자. 

이제 $(2N-1) \times 2$ 격자 내부에서 관찰을 해보자. 각 행별로 같은 색의 영역을 하나로 묶고 정점을 부여해주자. 정점의 색은 묶은 영역들의 색으로 정의한다. 변을 공유하는 같은 색의 정점들을 간선으로 이었을 때, 그래프에는 사이클이 없다. 각 컴포넌트에 대해 정점에 대응하는 영역의 우변이 가장 왼쪽에 있는 정점의 최대 차수가 $1$이기 때문이다. 이런 리프 정점들을 순차적으로 제거해주면 컴포넌트가 트리 형태라는 것을 알 수 있다.

가장 왼쪽 우변을 가진 정점은 차수가 최대 1이다.

따라서 정점 개수와 간선의 개수를 알고 있으면 컴포넌트 개수를 구할 수 있다.

 

간선은 같은 색의 $(i, 1)$과 $(i, 2)$ 사이에 생긴다. $S'_{i, j}$를 만드는 과정을 생각해보면 $S'_{i, 1} = S'_{i+1, 1}$이거나 $S'_{i, 2} = S'_{i+1, 2}$이다. 이는 $(i, 1)$과 $(i+1, 1)$의 색이 다른 것과 $(i, 2)$와 $(i+1, 2)$의 색이 다른 것이 동시에 일어나는 경우는 없다는 것을 의미한다.

$s_i$을 $(i, 1)$과 $(i, 2)$의 색이 같으면 $1$, 다르면 $0$으로 정의하자. $s_i \neq s_{i+1}$인 $i$의 개수는 ($(i, 1)$과 $(i+1, 1)$의 색이 다른 $i$의 개수) + ($(i, 2)$와 $(i+1, 2)$의 색이 다른 $i$의 개수)로 구할 수 있다.

 

($(i, j)$과 $(i+1, j)$의 색이 다른 $i$의 개수)는 $j$번째 행에 있는 정점 개수$-1$과 같다.

따라서 각 행에 대해서 정점 개수를 알고 $(1, 1)$과 $(1, 2)$의 색이 같은지 여부를 알고 있으면 간선의 개수를 $O(1)$에 알 수 있다.

 

간선의 개수를 구하기 위해 필요한 정보들은 쿼리에 대해 $O(1)$에 갱신할 수 있기 때문에 전체 문제를 $O(N+Q)$에 해결할 수 있다.

D. Graceful Triangles

각 삼각형에 대해 빨간 변에 쓰인 숫자가 나머지 두 변에 쓰인 숫자의 합이 되도록 하자.

빨간 변에는 오른쪽부터 $2N-1, 2N-2, \cdots 2N-k$를 적자. ($k$는 빨간 변 개수이다)  

나머지 삼각형들에 대해서 왼쪽부터 합이 $2N-k, 2N-k+1, \cdots, 2N-1$인 쌍을 2개씩 만들어야 한다.

처음에 $l=1, r=2N-k-1$로 하자. $l+r$과 합이 같은 쌍을 만들기 위해서는 $l=l+1, r=r-1$을 해주면 된다. 한 변이 겹치고 합이 $1$ 큰 쌍을 만들기 위해서는 $l=l+1, r=r$을 해주면 된다. 다음은 $n=8$에 대한 예시이다.

 

이제 변의 값에 맞추어서 각 정점의 값을 배정하면 된다.

E. Hexagonal Tiling

 

단위 정삼각형을 정점으로 보고, 변을 공유하는 정삼각형들 사이에 간선을 놓자. 이 그래프는 이분그래프이다. 이제 min cost bipartite matching을 해주면 TLE가 난다. 이는 의도된 풀이가 아니지만 $n \leq 100$이고 TL이 4초라서 본 대회에서 제출한 사람이 많은 듯하다.

마름모를 모두 배정했다고 하자. 각 행에 온전히 포함된 마름모는 정확히 $N$개 있다. 

 

pf) 행에 대한 귀납법을 사용하자. 1번 행에 대해서는 자명하다.

 

$i \leq 2$번 행에 대해서, $i-1$번 행에는 행에 온전히 포함된 마름모가 $N$개 있다.

그리고 $i-1$번 행에 있는 역삼각형이 아닌 정삼각형의 개수와 $i$번 행에 있는 역삼각형의 개수가 같다.

$i-1$번 행과 $i$번 행에 걸친 마름모의 개수는 ($i-1$번 행에 있는 역삼각형이 아닌 정삼각형 개수) - $N$ 이고, $i$번 행에 있는 역삼각형 중 두 행에 걸친 마름모에 포함되지 않는 역삼각형 개수는 $N$개이다. 이는 $i$번 행에 온전히 포함된 마름모의 개수와 같다.

한 행에 포함된 마름모에 대해서, 밑변에서 윗변으로 화살표를 그려주자. 그러면 $N$개의 겹치지 않는 경로가 완성된다.

이를 이용해서 network flow를 다음과 같이 모델링해주자. 각 간선의 용량은 1이다.

 자세하게 그래프를 살펴보자. 각 길이 1의 가로 선분에 대해서 노드를 2개 배정해주었다. 아래 노드에서 윗 노드로 간선을 배치해서 최대 1의 유량이 흐를 수 있도록 했다.

 

두 가로 선분을 잇는 간선에 대해서, 두 가로 선분으로 만들 수 있는 마름모를 $S_1$, 윗 가로 선분을 중심으로 위 아래에 있는 삼각형을 합쳐서 만든 마름모를 $S_2$라고 하자.

두 가로 선분을 잇는 간선의 비용은 ($S_1$의 비용 - $S_2$의 비용)이다. flow를 흘리기 전에는 가로 선분을 기준으로 위아래에 있는 삼각형을 합친 마름모를 모두 선택한 다음에, 간선에 유량이 1 흐를 때마다 $S_2$를 제거하고 $S_1$을 추가한다고 생각하면 좋다.

 

이제 mcmf를 돌려주면 된다. Bellman-ford 알고리즘을 사용하면 $O(VEf) = O(N^5)$으로 TLE가 난다. Potential method를 사용해주면 $O(ElogVf)=O(N^3logN)$에 문제를 해결할 수 있다. 아직 potential method를 모르고 있었다면 이번 기회에 알아보자. 재미있는 기법이다.

F. Jenga Game

010, 101 층에서는 아무 블럭도 제거할 수 없다.

110, 011에서는 블럭을 정확히 1개 제거할 수 있다. 이런 층을 타입 1이라고 하자.

111에서는 블럭을 1개 또는 2개 제거할 수 있다. 이런 층을 타입 2라고 하자.

 

타입 1 층의 개수를 $c_1$, 타입 2 층의 개수를 $c_2$라고 하자.

$dp[i][j]$를 $c_1=i, c_2=j$일 때 선공 승리 여부로 두자.

 

$dp[i][j] = \sim dp[i-1][j] \lor \sim dp[i+1][j-1] \lor \sim dp[i][j-1]$이다. 이 점화식을 통해 규칙을 찾으면 $c_1$과 $c_2$가 모두 짝수일 때는 후공이 이기고 나머지 경우에는 선공이 이긴다.

Sprague-grundy Theorem을 사용하면 0.999초만에 풀린다.

G. Make RUN Great Again

RUN의 점수를 $t$로 할 수 있는지 여부를 판단해보자. 각 동아리에 대해서, $\max (0, (a_i-t)b_i)$의 skeptism factor의 증가가 일어난다. 다 합해주면 $O(N)$에 가능 여부를 판단할 수 있다.

 

$t$가 증가할 수록 필요한 skeptism factor가 증가하므로, $t$에 대한 이분탐색을 실행해주면 $O(Nlog(10^6))$에 문제를 해결할 수 있다.

H. Mosaic

해당 문제의 깔끔한 풀이를 아직 알아내지 못했다. 추후에 알아내게 된다면 적도록 하겠다.

I. Mukjjippa

$dp[i][j]$을 $i$번째 턴에 $i$가 attacker일 확률이라고 하자. $j=0$이면 attacker가 없는 것이다. $dp[i][A] \times$ ($i+1$번째 턴에 비길 확률)을 합하면 답을 구할 수 있다.

 

$dp[i+1][j] = (dp[i][0] + dp[i][A] + dp[i][B]) \times$ ($i+1$번째 턴에 $j$가 이길 확률)이다.

$dp[i+1][0] = dp[i][0] \times $ ($i+1$번째 턴에 비길 확률)이다.

따라서 전체 문제를 $O(N)$에 해결할 수 있다.

J. Running in the Plane

답은 $3$ 이하이다. (0, 1), (1, 0), (-1, -1)을 사용하면 임의의 격자점을 방문하고 원점으로 되돌아올 수 있다.

답이 $1$인 것을 판별하는 것은 쉽다. 원점에서 점으로 이은 반직선들이 모두 같은지 확인해주면 된다.

모든 점들이 중심을 지나는 직선 위에 있다면 답이 $2$ 이하이다. 이제 모든 점들이 원점을 지나는 직선 위에 있지 않다고 하자.

 

답이 $2$인 것을 판별하는 것은 조금 어렵다. $(u_1, v_1), (u_2, v_2)$로 모든 점을 방문하고 싶다고 하자. 

두 벡터를 연장해서 얻는 영역 안에 점들이 있어야 한다. 따라서 답이 $2$이기 위해서는 모든 점들이 한 반평면 안에 있어야 한다(경계 미포함).

 

이제 모든 점들이 반평면 안에 있으면 답이 $2$임을 보일 것이다. 벡터 $(u, v)$를 기준으로 모든 점들이 $(u, v)$와 $(-u, -v)$가 이루는 반평면 안에 있다고 하자.

 

$(-u, -v)$를 잇는 직선 위에 있는 격자점들을 제외하고 반평면 내부에 있는 모든 점들을 방문할 수 있도록 새로운 벡터를 good set에 추가할 것이다. $vx-uy=1$을 만족하는 (x, y)와 적당히 큰 $k$에 대해서 $(x, y) - k(u, v)$를 새로운 벡터로 추가해주면 된다. (x, y)는 확장 유클리드로 구할 수 있다. 

 

따라서 전체 문제를 $O(N+log10^8)$에 해결할 수 있다. 

K. Same Segment

포함관계에 있는 구간이 존재하지 않으면 가장 왼쪽 구간의 끝칸에 $K$를 더한 뒤에 해당 칸을 포함하는 모든 구간을 제거하는 것을 반복함으로써 해를 구할 수 있다.

 

구간 $[l_1, r_1]$이 구간 $[l_2, r_2]$를 포함한다고 하자. $l_1 \leq i < l_2$ 혹은 $r_2 < i \leq r_1$을 만족하는 $i$에 대해서 $a_i=0$을 만족해야 한다. $a$에서 $[l_1, l_2)$와 $(r_2, r_1]$을 제거해주자. 문제에서 주어진 구간들은 원소 제거 이후에도 여전히 구간을 이루거나 제거된 원소들에 포함된다. 만약 제거된 원소들에 포함된다면 해당 구간의 합을 $K$로 만들어주지 못하기 때문에 해가 존재하지 않는다.

 

위와 같이 원소들을 제거해주는 시행을 반복해보자. 결론은 두 가지 중 하나인데, 어떤 구간이 제거되는 원소들에 포함되어서 해가 존재하지 않게 되거나, 포함관계에 있는 원소들이 더 이상 없게 되어서 해가 존재하게 된다. 이때 중요한 것은 해의 존재성이 $K$와 무관하다는 것이다. 따라서 $K=1$로 생각하고 문제를 풀 수 있다.

앞에서부터 $a_i$를 정해보자. $dp[i]$를 $a_1$부터 $a_i$까지 정했을 때 $a_i=1$을 만족하고 모순 없이 채울 수 있는지 여부로 정의하자. 여기에서 모순은 다음을 의미한다.

• 어떤 구간 $[l, r]$가 존재해서 $[l, r]$ 내부 합이 $2$ 이상이다.
• $l \leq r \leq i$인 구간 $[l, r]$가 존재해서 $\sum_{i=l}^r a_i = 0$이다.

이러한 dp의 전이는 어떻게 될까? $j$에서 $i$로 전이되기 위해서는 다음과 같은 조건이 만족되어야 한다.

• $j$와 $i$를 포함하는 구간이 없다.
• $j$와 $i$ 사이에 구간이 없다.

이러한 조건을 만족하는 $j$는 구간의 형태로 나타난다. 해당 구간을 two pointer를 통해서 구해주면 segment tree를 사용하거나 $dp[i]=1$인 $i$의 집합을 std::set으로 관리해서 전체 문제를 $O(NlogN)$에 해결할 수 있다.

L. Simple Tree Decomposition Problem

knapsack 형태의 tree dp는 $O(NB^2)$의 시간이 필요하다. Tree optimization을 사용하면 $O(NB)$에 풀 수 있다. 제목처럼 simple한 풀이이다.

M. White Black Tree

간선 $e$와 색깔 $c$에 대해서 간선을 기준으로 나눈 두 서브트리에 모두 색이 $c$인 간선이 존재하는지 여부를 $f(e, c)$라고 하자. 

Edge cost는 $\sum_{e \in E} \sum_{c=B, W} [f(e, c)]_1$로 구할 수 있다. $[x]_1$은 $x$가 참이면 $1$, $x$가 거짓이면 $0$으로 정의하자.

 

Total cost가 감소하기 위해서는 어떤 operation에 대해서 edge cost가 2 이상 감소해야 한다. 

 

간선 $e$의 양 끝 정점의 색을 swap하면 $f(e, B), f(e, W)$만 바뀌고 나머지 edge cost는 유지된다. operation을 통해 edge cost가 2 이상 감소하기 위해서는 swap 전에는 $f(e, B)=f(e, W)=true$이어야 하고 swap 후에 $f(e, B)=f(e, W)=false$이어야 한다. 이는 $e$를 기준으로 한쪽에는 흰색 정점들이, 다른 쪽에는 검은색 정점들이 몰려있다는 뜻이다.

 

$e$를 제외한 나머지 간선 $w$는 $[f(w, B)]_1+[f(w, W)]_1 \geq 1$을 만족한다. 따라서 $e$를 기준으로 한쪽에 흰색 정점들이, 다른 쪽에는 검은색 정점들이 몰려있으면 edge cost는 $N-2$로 최솟값을 가진다. $e$의 양끝 정점들의 색을 swap한 이후에는 operation을 실행하지 않는 것이 최적이다.

 

각 간선 $e$에 대해서 $e$를 기준으로 한쪽 서브트리에는 흰색 정점을, 다른 쪽 서브트리에는 검은색 정점을 배치하는 cost를 구한 뒤 초기 tree의 cost와의 최솟값을 구해주면 된다. 이는 이 문제를 통해서 할 수 있다. 간단한 rerooting tree dp를 해주면 된다. 따라서 문제를 $O(N)$에 해결할 수 있다.