교육용으로 사용한 10문제의 풀이입니다. 용어가 원본 문제와 다를 수 있습니다.
BAPC 2021 F. “Fair Play”
$n$이 홀수인 경우는 당연히 불가능하고, 짝수인 경우 $(b, p)$를 std::pair 와 같은 방식으로 정렬한 것을 $(b_{1}, p_{1}), \cdots, (b_{n}, p_{n})$이라고 둡시다. 이 때 유일하게 가능한 매칭 방법은 $(b_{1}, p_{1})$을 $(b_{n}, p_{n})$과, $(b_{2}, p_{2})$를 $(b_{n-1}, p_{n-1})$과 … 매칭해주는 것입니다. 이렇게 해서 벡터합이 모두 균일하다면 possible, 그렇지 않다면 impossible 입니다.
BAPC 2021 I “Implementation Irregularities”
$s_{i}$가 증가하는 순서대로 원소들을 배열하고, $s_{i} = -1$인 원소들을 제외합시다. 이 때 답은 $\max_{i} \lceil \frac{t_{1} + \cdots + t_{i}}{s_{i}} \rceil$가 됩니다.
2021/2022 COCI Contest #2 B “Kutije”
한 순열 $p(1), \cdots, p(n)$에 대해 $i$번 정점과 $p(i)$번 정점을 간선으로 이어주면, 이는 사이클 몇 개로 분할되는 그래프를 이룹니다. 결국 주어지는 쿼리는 $a, b$가 같은 연결컴포넌트에 있는지를 물어보는 것이고, 사전에 DFS, union-find를 통해 컴포넌트를 구해두면 쿼리당 $O(1)$에 해결할 수 있습니다.
CERC 2015 K “Kernel Knights”
Indegree가 0인 정점 $a$는 무조건 선택해야 하고, 따라서 $f_{a}$는 무조건 배제해야 합니다. 이제 전체 그래프에서 $a, f_{a}$를 제외한 뒤 같은 과정을 반복하면 최종적으로 아무 정점도 남지 않거나, cycle이 남게 됩니다. 그래프가 이분그래프이기 때문에 이는 짝수 길이 cycle이 되고, 이 중에서는 범위($[1, N]$ 혹은 $[N+1, 2N]$)가 같은 점들만 골라주면 됩니다.
2020 Jakarta Regional J “Token Distance”
좀 더 쉬운 버전인, 어떤 구간 $[s, e]$를 정렬했을 때 $\set{x, x + 1, \cdots, x + e - s}$가 될 필요충분조건을 생각해 봅시다.
- 구간 $[s, e]$의 최댓값 - 최솟값이 정확히 $e - s$이다.
- 구간 $[s, e]$에 중복 원소가 존재하지 않는다.
하지만 일반적으로 $\set{x, x + g, \cdots, x + g (e - s)}$를 이룰 조건은 위 두개만으론 불충분합니다. 이 때 다음이 성립합니다.
Proposition. 구간 $[s, e]$의 수를 $A_{s}, \cdots, A_{e}$라고 하자. 다음 세 조건을 동시에 만족하는 것과, $\set{A_{s}, \cdots, A_{e}} = \set{x, x + g, \cdots, x + g(e-s)}$가 성립하는 것은 동치이다.
- $\max(A_{s}, \cdots, A_{e}) - \min(A_{s}, \cdots, A_{e}) = g(e-s)$.
- $A_{s}, \cdots, A_{e}$중 중복되는 값이 존재하지 않는다.
- $\gcd(A_{s} - A_{s+1}, A_{s+1} - A_{s+2}, \cdots, A_{e-1} - A_{e}) = g$.
$\set{A_{s}, \cdots, A_{e}} = \set{x, \cdots, x + g(e-s)}$가 성립하는 경우 $\gcd$ 조건을 만족하게 됩니다. $\gcd$는 $g$의 배수가 될 것이고, 정확히 $g$가 아니면 $A_{s} \pm g$가 등장할 수 없기 때문입니다. 또한 $\gcd$ 조건을 만족하는 수열은 모두 $\set{x, \cdots, x + g(e-s)}$의 재배열뿐입니다.
위 세가지 조건은 모두 Segment Tree 등을 이용해 판별할 수 있고, 시간복잡도는 $O(N \log N)$이 됩니다.
2021/2022 COCI Contest #2 E “Osumnjičeni”
주어진 $i$에 대해서, 구간 $[L_{i}, R_{i}], \cdots, [L_{j}, R_{j}]$가 서로소가 되는 $j$의 최댓값을 미리 구해두고, 이를 $p(i)$라고 합시다. $p(i)$는 two-pointer로 $O(N\log N)$ 시간에 구할 수 있습니다.
$p^{0}(i) = i, p^{k}(i) = p(p^{k-1}(i))$로 정의하면, $[s, e]$ 형태로 쿼리가 들어올 경우 답은 $p^{k}(s) \ge e$를 만족하는 $k$의 최솟값이 됩니다. 이는 $p^{k}(i)$를 sparse table 등으로 구해두면 $O(N \log N + Q \log N)$ 시간에 해결할 수 있습니다.
DMOPC ‘21 Contest #7 Problem 5, “King’s Commands”
보다 간단한 경우로 $\deg(a, 0) + \deg(a, 1) \le 1$인 경우를 생각해 봅시다. 연결 컴포넌트의 개수는 Degree가 0인 정점 (lone vertex)의 수와 선분들의 연결 컴포넌트 개수의 합으로 나타낼 수 있습니다.
만약 $\deg(a, 0) + \deg(a, 1) \le 1$이라면, lone vertex의 수는 상수로 유지되는 것을 알 수 있습니다. 따라서 선분들의 컴포넌트 수를 최소화하는 데만 집중하면 됩니다.
$(l, 0), (r, 1)$을 잇는 선분을 $[l, r]$로 표기합시다. (편의상 $l \le r$을 가정합니다) 만약 $l’ \le l \le r \le r’$을 만족하는 $[l’, r’]$이 존재할 경우 $[l, r]$은 어떻게 놓아도 $[l’, r’]$과 이어지므로 신경쓰지 않아도 됩니다. 따라서 모든 선분들을 $l$ 순으로 정렬한 것을 $[l_{1}, r_{1}], \cdots, [l_{n}, r_{n}]$이라고 두면 $r_{1} < r_{2} < \cdots < r_{n}$을 가정할 수 있습니다. 마찬가지로 $l_{1} < l_{2} < \cdots < l_{n}$ 또한 가정할 수 있습니다.
만약 $r_{k} \lt l_{k+1}$이라면 어떻게 하더라도 두 선분 $[l_{k}, r_{k}]$와 $[l_{k+1}, r_{k+1}]$을 이을 수 없고, $r_{k} > l_{k+1}$이라면 둘을 엇갈리게 놓아서 연결할 수 있습니다.
이제 본 문제를 해결해 봅시다. 차수가 2인 경우에는 간선을 어떻게 배치하느냐에 따라 lone vertex의 수가 달라질 수 있습니다. 이 때 간선들을 bottom vertex에 따라 정렬하고, 연속한 간선들을 group $G_{1}, G_{2}, \cdots, G_{k}$로 최대한 쪼갭시다. 이 때 모든 $1 \le i \lt k$에 대해 $G_{1}, \cdots, G_{i}$의 top vertex 중 가장 오른쪽에 있는 것이 $G_{i+1}, \cdots, G_{k}$의 top vertex 중 가장 왼쪽에 있는 것보다 작거나 같아야 합니다. 이 때 각 group의 간선들은 차수 2인 정점 없이, 모두 연결되도록 할 수 있습니다. group $G_{i}$까지 모두 연결되도록 했을 때, 어떤 정점 $x$가 존재하여 $G_{i}$의 간선과 $G_{i+1}$의 간선에 모두 연결된다고 합시다. 이 경우 $G_{1}, \cdots, G_{i}$를 모두 뒤집어주면 컴포넌트의 개수는 최대 1 감소하는 반면, lone vertex의 수는 확실히 1 감소하여 답이 줄어들지 않습니다.
즉, 답이 $k$인 간선 배치가 주어지면 답이 $k$ 이상이고 차수 2인 정점이 없는 배치를 만들 수 있으므로, 우리는 차수 2인 정점이 없는 배치 중 컴포넌트 갯수가 가장 적은 배치를 찾을 것입니다.
어떤 점 $(a, 0), (a, 1)$에 연결된 간선이 2개라면, 두 간선이 연결된 점은 달라야 합니다. 모든 정점 $(a, \ast)$의 차수가 $2$ 이하이므로, 이런 구조에서는 path와 cycle만이 존재합니다. 이 중에서 우리는 $v_{1} \lt v_{2} \lt \cdots < v_{q}$를 차례로 잇는 simple increasing path들만을 먼저 생각합시다.
Simple increasing path들로 분할하고 나면 문제가 한층 쉬워집니다. 이제 각 정점의 차수는 1 이하가 되고, 앞서 다룬 케이스에 따라 엇갈리게 Path들을 놓으면 됩니다. 다만 이 경우에, $l’ \le l \le r \le r’$을 만족하는 두 chain $[l’, r’]$, $[l, r]$에 대해 $[l, r]$을 그냥 버리면 안됩니다.
Simple path가 아닌 path나 cycle의 경우, 사실상 simple path와 동등하게 생각할 수 있습니다. 상세한 증명은 원 editorial https://dmoj.ca/problem/dmopc21c7p5/editorial 을 참고하시기 바랍니다.
KTH challenge 2015 H “The Addition Game”
길이 $n$의 수열 $a$가 주어지면, $\pi + \sigma = a \pmod{n}$을 만족하는 $\pi, \sigma$를 찾아야 합니다. 이야기하기 쉽게, $a - \pi$가 순열이 되는 $\pi$를 찾는 문제로 생각합시다. 당연히 $a_{1} + \cdots + a_{n} = 0 \pmod{n}$이어야 해가 존재하고, 놀랍게도 이 조건만 만족하면 해가 존재합니다. 이 문제에는 잘 통하는 휴리스틱과 어려운 정해가 있습니다.
Heuristic
$a - \pi$가 순열이 아니라면, $a - \pi$에 두 번 이상 등장하는 수 $k$와 한 번도 등장하지 않는 수 $l$이 존재합니다. 이 때 $k = (a - \pi)_{i}$를 만족하는 $i$와, $a_{i} - \pi_{j} = l$을 만족하는 $j$를 잡고 $\pi_{i}, \pi_{j}$를 swap하면 $l$의 개수가 하나 늘어나고, $k$의 개수는 감소하거나 유지됩니다. 이 방법의 단점은 $m = a_{j} - \pi_{j}$의 개수가 $0$개로 줄어들거나 $p = a_{j} - \pi_{i}$의 개수가 늘어날 수 있다는 점인데, 적절히 구현하면 놀랍게도 만점을 받을 수 있습니다.
Deterministic
$a = \mathbf{0}$이라고 생각합시다. 이 경우에는 $\pi_{i} = i, \sigma_{i} = -i$로 두면 됩니다. 이제 이 상태에서 $\pi$에 적당한 swap을 통해 $a^{1} = (a_{1}, -a_{1}, 0, \cdots, 0) = \pi^{1} + \sigma^{1}$을 만들고, 다시 $\pi^{1}$을 적당히 재배열해서 $a^{2} = (a_{1}, a_{2}, -a_{1}-a_{2}, 0, \cdots, 0) = \pi^{2} + \sigma^{2}$를 만드는 방식을 $n-1$번 반복할 수 있습니다. 각 단계에서 $\sigma^{k} = a^{k} - \pi^{k}$ 역시 순열이어야 합니다. 이렇게 과정을 분해하는 까닭은 값이 2개만 틀려 있을 때만 문제를 해결해도 충분하다는 것을 이야기하기 위함입니다.
보다 일반적으로, $\pi(i_{1}) + \sigma(i_{1}) \neq a(i_{1})$, $\pi(i_{2}) + \sigma(i_{2}) \neq a(i_{2})$라고 하고, $i \neq i_{1}, i_{2}$에 대해 $\pi(i) + \sigma(i) = a(i)$라고 합시다. 따라서 $\pi(i_{1}) + \pi(i_{2}) + \sigma(i_{1}) + \sigma(i_{2}) = a(i_{1}) + a(i_{2})$가 성립합니다.
편의상 어떤 배열 $b$의 값 $b(i_{1})$ (혹은 $b(i_{2})$)와 다른 위치 $j \neq i_{1}, i_{2}$의 값 $b(j)$를 swap하는 것을 $b(i_{1})$을 “넣고” $b(j)$를 “빼낸다"라고 표현하겠습니다.
만약 $\pi(i_{1}) + \sigma(i_{\ast}) = a(i_{1})$이 성립한다면 끝입니다. 그렇지 않다면 $\pi(j_{1}) + \sigma(i_{1}) = a(i_{1})$을 만족하는 $j_{1} \neq i_{1}, i_{2}$이 유일하게 존재합니다. 따라서 $a(i_{1})$과 $\sigma(i_{1})$을 넣고, $a(j_{1})$과 $\sigma(j_{1})$을 빼냅시다. 이는 $\pi(i_{1})$과 $\pi(j_{1})$을 swap하는 것과 동치인 연산입니다.
여전히 빠져나온 $\pi$의 두 원소를 적당히 swap해서 조건을 만족하는 수열을 만들 수 없다면 이번에는 $a(j_{1}), \sigma(i_{2})$를 넣어줍시다. $a(j_{1}), \sigma(j_{1})$을 넣으려고 시도하면 결국 원래 넣었던 $a(i_{1})$이 빠져나올테니까요. 빠져나온 수를 $a(j_{2}), \sigma(j_{2})$라고 둡시다. $a(i_{2})$는 넣지 않고 남겨둘 겁니다.
결국 $k \ge 3$번째 step에서는 $a(j_{k-1}), \sigma(j_{k-2})$을 넣고, $a(j_{k}), \sigma(j_{k})$를 빼내는 과정을 반복하게 됩니다. 이 과정이 무한히 반복될 수 없음을 보입시다. $\pi(j_{1}), \cdots, \pi(j_{t})$는 모두 distinct하지만 $\pi(j_{s}) = \pi(j_{t+1})$을 만족하는 $s \le t$가 존재할 것입니다.
이 때 $t+1$번째 step에서 빠져나오는 인덱스가 바로 $j_{s}$가 되는데, $j_{s}$가 빠져나올 당시 대신 넣어준 수는 바로 $a(j_{s-1}), \sigma(j_{s-2})$입니다. 따라서 관계식
$ \pi(i_{1}) + \pi(i_{2}) + \sigma(j_{t}) + \sigma(j_{s-2}) = a(i_{2}) + a(j_{s-1}) $ 이 성립하게 됩니다. 한편 $s$번째 step에서
$ \pi(i_{1}) + \pi(i_{2}) + \sigma(j_{s-1}) + \sigma(j_{s-2}) = a(i_{2}) + a(j_{s-1}) $
이 성립하므로, $\sigma(j_{s-1}) = \sigma(j_{t})$가 됩니다. 이 때 $\pi(j_{1}), \cdots, \pi(j_{t})$가 모두 distinct하고 $\pi, \sigma$는 모두 순열이므로 모순이 발생합니다. 따라서 step은 최대 $n-2$번 지속될 수 있고, 총 $O(n^2)$ 시간에 문제를 해결할 수 있습니다.
CERC 2017 E “Embedding Enumeration”
$D_{x}$를 $x$가 왼쪽 위 모서리에 위치할 때 $x$의 서브트리를 배치하는 방법의 수라고 합시다. 당연히 $x$의 차수는 $2$ 이하여야 하고, 모든 정점의 차수는 $3$ 이하여야 합니다.
$x$가 리프인 경우는 $D_{x} = 1$이므로, $x$가 자식이 $1$개 또는 $2$개인 경우만 고려하면 됩니다.
자식이 2개인 경우
$x$의 두 자식을 $h, v$라고 하고, 일반성을 잃지 않고 $h$가 오른쪽으로, $v$가 아래로 뻗는다고 합시다. $v$는 자식이 최대 1개여야 합니다. 자식이 있다면 그걸 $v_{0}$라고 두면, $h$와 $v_{0}$가 격자의 가장 왼쪽 칸을 채우게 됩니다. 이 때 아래 케이스를 이용해 처리해줍니다.
Important Subcase: “Two Heads Case”
어떤 두 정점 $a, b$가 격자의 왼쪽 칸을 메우고 있을 때, 두 정점의 서브트리를 배치하는 경우의 수를 생각해 봅시다. 편의상 $a$의 서브트리 크기 $s_{a}$가 $b$의 크기 $s_{b}$보다 작다고 합시다.
그렇다면 $a$는 길이 $s_{a}$의 직선이어야만 합니다. 또한 $b$도 길이 $s_{a}$의 직선을 직속 서브트리로 가져야 합니다. 이 때 $b$의 $s_{a}$번째 자식을 $b’$이라고 두면, $D_{b’}$이 답이 됩니다.
자식이 1개인 경우
만약 $x$의 서브트리가 직선이라면, 고려해줄 특이 케이스가 있습니다. 거꾸로 된 ㄷ자 모양으로 격자를 채우는 경우인데, DP의 특성상 $x$의 서브트리 크기가 홀수일 때만 $D_{x}$에 1을 더해주는 걸로 충분합니다.
이외의 경우, $x$의 서브트리 중에서 자식이 둘인 깊이가 가장 작은 정점 $h$가 존재합니다. 역시 $h$에서 케이스 처리를 해주면 됩니다.
시작부터 방향을 아래쪽으로 틀어 채우는 경우, $x$와 $h$의 깊이 차이가 2 이상이어야 합니다. $x$의 grandson을 $y$라고 두면, $D_{y}$를 더해줍니다. 이는 $x$에서 $h$의 grandparent 사이에 방향을 전환하는 모든 경우를 아우르고 있습니다.
$h$의 부모 정점에서 방향을 아래쪽으로 트는 경우, $h$의 두 자식 $u, v$ 중 하나는 왼쪽의 빈 공간으로 보내야 합니다. 따라서 둘 중 하나는 크기가 작은 직선이어야 합니다. $u$를 보낸다고 하면 $D_{v}$가 답이 될 것입니다.
$h$까지 방향을 틀지 않는 경우, $h$의 두 자식 $u, v$ 중 하나를 아래로 보냅니다. $v$를 보낸다고 할 때, $v$는 자식이 둘이어도 됩니다. 다만 두 자식 중 하나는 왼쪽의 빈 공간을 채워야 하므로, 크기가 작은 직선이어야 합니다. 왼쪽으로 보내지 않는 자식을 $v_{r}$이라고 할 때, $u, v_{r}$을 이용해 Two Head Case를 처리해 주면 됩니다.
디테일을 다소 생략하였으나, 전체 케이스를 $O(N)$에 구현할 수 있습니다.
JAG Summer Camp 2013 Day 4 J “Rotation Game”
우선 wild-card 문자 *가 없는 경우를 처리해봅시다. 만약 시작 문자열에 o가 있는 칸에 도착 문자열에는 .가 있다면 그 칸에 +, 반대로 시작 문자열에는 .가 있고 도착 문자열에는 o가 있다면 -를 적어줍시다. +와 -의 개수는 같다고 가정해도 됩니다.
문제에서 가능한 변환들이 주는 의미는 결국 하나의 +를 한 열 움직이는 데 1번의 회전이 필요하다는 것입니다. 또, 한 번의 회전이면 + 한개를 다른 +들에 영향을 미치지 않고 이동시킬 수 있다는 의미이기도 합니다.
이렇게 되면, 모든 +와 모든 -를 가장 거리가 가까운 것끼리 매칭시켜주고, 매칭된 +, - 사이 거리의 합이 최적해인 것처럼 보입니다. 이는 stack을 이용해 잉여 +, 잉여 -를 관리하면 $O(N)$에 매칭해줄 수 있습니다.
하지만 몇 가지 예외 케이스가 있는데, 바로 +, -가 같은 열에 있는 경우, 또 아래와 같이 +-와 -+이 맞물려 있는 경우입니다.
첫 번째로 +-가 한 열에 맞물려 있는 경우, 단순히 같은 열의 +, -를 비용 0으로 이어주면 안됩니다. 하지만 이 열보다 왼쪽에 잉여 +가 존재할 경우 이 열의 -를 잉여 +에 매칭해 주고, 이 열의 +를 잉여 +로 남기면 됩니다. 잉여 -가 존재하는 경우도 마찬가지입니다. 따라서 이 열 왼쪽에 잉여 +, -가 존재하지 않는 경우에만 비용에 1을 더해줍니다.
두 번째로 +-, -+이 맞물려 놓이는 경우, 회전 한 번으로 두 열을 모두 돌릴 수 있습니다. 이 역시도 왼쪽에 잉여 +, 잉여 -가 없는 경우에만 성립합니다. 따라서 +-, -+, … 이 교대로 $k$번 반복될 경우, 비용에 $\lceil k / 2 \rceil$을 더해주면 됩니다.
wild-card *가 있는 경우에도 이 풀이를 자연스럽게 확장할 수 있습니다. $D(i, j, u, d)$를 $i$번째 열까지 봤고, 잉여 +가 $j$개이며, ($j < 0$인 경우 잉여 -가 있는 것으로 봅니다) 직전 두 열이 각각 $u, d$인 경우 비용의 최솟값으로 두고 DP를 해결하면 됩니다.